Optimal graphs for chromatic polynomials Original Research Article

Let image be the collection of all simple graphs with image vertices and image edges, and for image let image be the chromatic polynomial of image. A graph image is said to be optimal if another graph image does not exist with image for all image, with strict inequality holding for some image. 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 image and image 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.