Article ID Journal Published Year Pages File Type
4650512 Discrete Mathematics 2008 12 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,