Two Chromatic Polynomial Conjectures

✍ Scribed by Paul Seymour

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 300 KB
• Volume: 70
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1997.1749

✦ Synopsis

dedicated to professor w. t. tutte on the occasion of his eightieth birthday

Let P(*) be the chromatic polynomial of a graph. We show that P(5) &1 P(6) 2 P(7) &1 can be arbitrarily small, disproving a conjecture of Welsh (and of Brenti, independently) that P(*) 2 P(*&1) P(*+1) and also disproving several other conjectures of Brenti. Secondly, we prove that if the graph has n vertices, then

approaching a conjecture of Bartels and Welsh that P(n) P(n&1) &1 e (e is 2.718281 ...).

1997 Academic Press

1. Introduction

Let G be a graph (in this paper, all graphs are finite and simple) and for * 1, let P(*) denote the number of *-colourings of G. (A *-colouring means a map ,: V(G ) Ä [1, ..., *] such that ,(u){,(v) whenever u and v are adjacent vertices.) We are concerned with two conjectures about P(*). The first is the following:

(1.1) Conjecture. For all integers * 1, P(*) 2 P(*&1) P(*+1).

This was proposed by Welsh (private communication) in the early 1970 's, and later, independently, by Brenti [2]. We shall show that (1.1) is false; indeed, in Section 2 we exhibit graphs with P(5) &1 P(6) 2 P(7) &1 arbitrarily small.

The second conjecture, due to Bartels and Welsh [1], is the following (e=2.7182818 ... is the base of natural logarithms):

(1.2) Conjecture. If |V(G )| =n then P(n) P(n&1) &1 e.