Proof of a chromatic polynomial conjecture
by
Dong Feng Ming
Massey University

Let P(G, \lambda) be the chromatic polynomial of a graph G with n vertices. Bartels and Welsh proposed the following conjecture in the fourth conference on Integer Programming and Combinatorial Optimisation(IPCO IV) in 1995:

P(G, n)(P(G, n-1))-1 >= nn/(n-1)n > e,

where e(=2.7182818...) is the base of of natural logarithms. Paul Seymour obtained the following result, which is very close to the conjecture:

P(G, n)(P(G, n-1))-1 >= 685/252(=2.7182539...).

I proved the above conjecture. In fact, a more general result was obtained:

(\lambda-1)nP(G, \lambda) >= \lambdanP(G, \lambda-1)

for any real number \lambda >= n. Moreover, if G is connected, then

(\lambda-2)n-1P(G, \lambda) >= \lambda(\lambda-1)n-2P(G, \lambda-1)

for any real number \lambda >= n.

Some interesting inequalities on chromatic polynomials can be deduced by applying the above results:

\frac \lambda\lambda-(1-e-1)n < \frac P(G, \lambda)P(G, \lambda-1) <= \frac \lambda\lambda-n,

for any real number \lambda >= n, and

\lambda-d(x) <= \frac P(G, \lambda)P(G-x, \lambda) <= \lambda-(1-e-1)d(x),

for any vertex x in G and real number \lambda >= n-1, where d(x) is the degree of x in G and G-x is the graph obtained from G by deleting the vertex x and all edges incident with x.

Date received: June 10, 1999