A zero-free interval for chromatic polynomials of graphs with $3$-leaf spanning trees

Thomas Perrett
Technical University of Denmark

PDF

Minisymposium: GENERAL SESSION TALKS

Content: The \emph{chromatic polynomial} $P(G,t)$ of a graph $G$ is a polynomial with integer coefficients which counts, for each non-negative integer $t$, the number of proper $t$-colourings of $G$. A real number $t$ is called a \emph{chromatic root} of $G$ if $P(G,t) = 0$. An interval $I\subseteq \mathbb{R}$ is called \emph{zero-free} for a class of graphs $\mathcal{G}$ if no $G \in \mathcal{G}$ has a chromatic root in $I$. It is known~[1] that $(-\infty,0)$, $ (0,1)$, and $(1,32/27]$ are maximal zero-free intervals for the class of all graphs, but one may find larger zero-free intervals for more restrictive classes. Indeed, Thomassen~[2] showed that for graphs with a Hamiltonian path, the interval $(1,t_1]$ is maximally zero-free, where $t_1 \approx 1.295$ is the unique real root of the polynomial $(t-2)^3 + 4(t-1)$. We build on the techniques of Thomassen to prove that, for graphs containing a spanning tree with at most three leaves, the interval $(1, t_2]$ is maximally zero-free, where $t_2 \approx 1.2904$ is the smallest real root of the polynomial $(t-2)^6 +4(t-1)^2(t-2)^3 -(t-1)^4$. \vspace{5mm} \noindent \textbf{References.} \begin{itemize} \item[{[1]}] B. Jackson, A zero-free interval for chromatic polynomials of graphs, \emph{Combin. Probab. Comput.} \textbf{2}, (1993) 325-336. \item[{[2]}] C. Thomassen, Chromatic roots and Hamiltonian paths, \emph{J. Combin. Theory Ser. B} \textbf{80}, (2000) 218-224. \end{itemize}

Back to all abstracts