Spring 2016

Dichotomy Theorems for Generalized Chromatic Polynomials

Thursday, March 31st, 2016 11:45 am12:30 pm

Add to Calendar

Evaluation of the chromatic polynomial is easy on finitely many points, and #P hard everywhere else. We call this the difficult point property $DPP$. Let $F$ be a graph property and $k$ be a positive integer. A function $f: V(G) \rightarrow [k]$ is an $F$-coloring if for every $i \in [k]$ the set $f^{-1}(i)$ induces a graph in $F$. The author and Boris Zilber have shown in 2006 that counting $F$-colorings with $k$ colors is a polynomial $P_F(G;k)$ in $k$. We show infinitely many examples of properties $F$, where $DPP$ holds for $P_F(G;k)$, and formulate several conjectures, including also multivariate graph polynomials.