Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423297 | Discrete Mathematics | 2015 | 9 Pages |
Abstract
If G is a k-chromatic graph of order n then it is known that the chromatic polynomial of G, Ï(G,x), is at most x(xâ1)â¯(xâ(kâ1))xnâk=(x)âkxnâk for every xâN. We improve here this bound by showing that Ï(G,x)â¤(x)âk(xâ1)Î(G)âk+1xnâ1âÎ(G) for every xâN, where Î(G) is the maximum degree of G. Secondly, we show that if G is a connected k-chromatic graph of order n where kâ¥4 then Ï(G,x) is at most (x)âk(xâ1)nâk for every real xâ¥nâ2+(n2âk2ân+k)2 (it had been previously conjectured that this inequality holds for all xâ¥k). Finally, we provide an upper bound on the moduli of the chromatic roots that is an improvement over known bounds for dense graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jason Brown, Aysel Erey,