![Counting Complexity and Phase Transitions_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Counting%20Complexity%20and%20Phase%20Transitions_hi-res.jpg?h=bf33d09a&itok=MrH5eN5T)
Abstract
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.