On upper bounds for real roots of chromatic polynomials

Abstract

For any positive integer n, let script G sign n denote the set of simple graphs of order n. For any graph G in script G sign n, let P(G,λ) denote its chromatic polynomial. In this paper, we first show that if G ∈ script G signn and χ(G)≤n-3, then P(G,λ) is zero-free in the interval (n-4+β/6-2/β,+∞), where β=(108+12√93)1/3 and β/6-2/β (=0.682327804...) is the only real root of x3+x-1; we proceed to prove that whenever n-6≤χ(G)≤n-2, P(G,λ) is zero-free in the interval (⌈(n+χ(G))/2⌉-2,+∞). Some related conjectures are also proposed. © 2003 Elsevier B.V. All rights reserved.