Upper Bound for the Coefficients of Chromatic polynomials

Publication date 27 February 2001

Coloring of graphs and hypergraphs (05C15)

Abstract: This paper describes an improvement in the upper bound for the magnitude of a coefficient of a term in the chromatic polynomial of a general graph. If

a_{r}

is the coefficient of the

q^{r}

term in the chromatic polynomial

P (G, q)

, where

q

is the number of colors, then we find

a_{r} l e e c h o o s e v - r - e - g + 2 c h o o s e v - r - g + 2 + e - k_{g} - g + 2 c h o o s e v - r - g + 2 - s u m_{n = 1}^{k_{g} - e l l_{g}} s u m_{m = 1}^{e l l_{g} - 1} e - g + 1 - n - m c h o o s e v - r - g - d e l t a_{g, 3} s u m_{n = 1}^{k_{g} + e l l_{g + 1}^{*} - e l l_{g}} e - e l l_{g} - g + 1 - n c h o o s e v - r - g

, where

k_{g}

is the number of circuits of length

g

and

e l l_{g}

and

e l l_{g + 1}^{*}

are certain numbers defined in the text.

This page was built for publication: Upper Bound for the Coefficients of Chromatic polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6470955)