Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650512 | Discrete Mathematics | 2008 | 12 Pages |
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
Italo Simonelli,