Building fences around the chromatic coefficients.

Abstract

Although these bounding conditions do not allow us to completely predict all chromatic polynomials, they do serve to severely limit the form of polynomials considered to be candidates for the chromatic polynomial of some graph.

In general it remains an unsolved problem to determine which polynomials are chromatic. The purpose of this paper is to establish controls over the allowable values and patterns in the coefficients of chromatic polynomials.

Associated to each graph G is its chromatic polynomial $f(G, t)$ and we associate to $f(G, t)$ the sequence $\alpha (G)$ of the norms of its coefficients. A stringent partial ordering is established for such sequences. First, we show that if H is a subgraph of G then $\alpha (H) \le \alpha (G).$ The main result is that for any graph G with q edges we have $\alpha (R\sb{q}) \le \alpha (G) \le (S\sb{q}), $ where $R\sb{q}$ and $S\sb{q}$ are specified graphs with q edges. It is also useful to examine the coefficient sequence $\beta (G)$ of a chromatic polynomial $f(G, t)$ which has been expressed in terms of falling factorials. If G has m missing edges we find that $\beta (T\sb{\bar m})\le \beta (G)\le \beta (X\sb{\bar m})$ where $T\sb{\bar m}$ and $X\sb{\bar m}$ are specified graphs with m missing edges.