Optimal graphs for chromatic polynomials

Abstract: Let be the collection of all simple graphs with vertices and edges, and for let be the chromatic polynomial of . A graph is said to be optimal if another graph does not exist with for all , with strict inequality holding for some . In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of and for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4. [Copyright &y& Elsevier]