Optimal graphs for chromatic polynomials

Let F(n,e)F(n,e) be the collection of all simple graphs with nn vertices and ee edges, and for G∈F(n,e)G∈F(n,e) let P(G;λ)P(G;λ) be the chromatic polynomial of GG. A graph G∈F(n,e)G∈F(n,e) is said to be optimal if another graph H∈F(n,e)H∈F(n,e) does not exist with P(H;λ)⩾P(G;λ)P(H;λ)⩾P(G;λ) 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 nn and ee 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.