Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Michael Young

Iowa State University

Reciprocity of Weak Chromatic Polynomials of Mixed Graphs

Abstract:

A \emph{mixed graph} is a graph with directed edges, called arcs, and undirected edges. A $k$-coloring of the vertices is \emph{proper} if colors $1,2,\ldots,k$ are assigned to each vertex such that vertices $u$ and $v$ have different colors if $uv$ is an edge and the color of $u$ is less than or equal to (resp. strictly less than) the color of $v$ if $uv$ is an arc. The \emph{weak (resp. strong) chromatic polynomial} of a mixed graph is a counting function that counts the number of proper $k$-colorings. This talk will discuss previous work on reciprocity theorems for other types of chromatic polynomials, and our reciprocity theorem for weak chromatic polynomials which uses partially ordered sets and order polynomials. This is joint work with Matthias Beck, Daniel Blado, Joseph Crawford, and Taina Jean-Louis.

Host: Jeff Remmel

November 20, 2012

3:00 PM

AP&M 7321

****************************