On upper bounds for real roots of chromatic polynomials (Q1827733): Difference between revisions

Let \(P(G, \lambda)\) denote the number of \(\lambda\)-colorings of graph \(G\), where \(\lambda\) is a positive integer. (\(P(G, \lambda)\) is a polynomial in \(\lambda\) with integer coefficients that alternate in sign.) For any positive integer \(n\), set \[ \beta_n = \begin{cases} 0, & 1\leq n\leq 4\\ 5/3 - \alpha/6 +10/(3\alpha), & n= 5\\ n - 4 +\beta/6 -2/\beta, & n\geq 6\\ \end{cases} \] where \(\alpha = (44+12\sqrt{69})^{1/3}\) and \(\beta = (108+12\sqrt{93})^{1/3}\). The authors prove that, for any graph \(G\) with \(n\) vertices, (1) if \(\chi(G)\leq n-3\) then \(P(G, \lambda) > 0\) for all \(\lambda > \beta_n\), and (2) if \(\chi(G) \leq n-k\), \(k= 1, 2, 3\), then \(P(G, \lambda) > 0\) for all \(\lambda > n-2-k\).