Do hypergraphs have properties on chromatic polynomials not owned by graphs

Ruixue Zhang, Fengming Dong

Published 2016-11-14Version 1

In this paper, we investigate chromatic polynomials of hypergraphs and find some properties which don't hold for chromatic polynomials of graphs. We first show that if $z$ is a zero of the independence polynomial of a graph $G$, then $1+1/z$ is a zero of the chromatic polynomial $P(H,\lambda)$, where $H$ is the hypergraph obtained from $G$ by adding a new vertex $w$ and changing each edge $\{u,v\}$ in $G$ to an edge $\{u,v,w\}$ in $H$. Thus we deduce that chromatic polynomials of hypergraphs have all integers as their zeros and contain dense real zeros in the set of real numbers and dense complex zeros in the whole complex plane. We then prove that for any multigraph $G=(V,E)$, the number of totally cyclic orientations of $G$ is equal to $|P(H',- 1)|$, where $H'$ is the hypergraph $(V',E')$ with $V'=V\cup E$ and $E'=\{\{u_e,v_e,e\}: e\in E\}$, where $u_e$ and $v_e$ are the two ends of $e$. Finally we show that the multiplicity of root "$0$" of $P(H,\lambda)$ may be at least $2$ for some connected hypergraphs $H$, and the multiplicity of root "$1$" of $P(H,\lambda)$ may be $1$ for some connected and separable hypergraphs $H$.