Article ID Journal Published Year Pages File Type
4649818 Discrete Mathematics 2009 10 Pages PDF
Abstract

For a graph GG, let P(G,λ)P(G,λ) be its chromatic polynomial. Two graphs GG and HH are chromatically equivalent, denoted G∼HG∼H, if P(G,λ)=P(H,λ)P(G,λ)=P(H,λ). A graph GG is chromatically unique if P(H,λ)=P(G,λ)P(H,λ)=P(G,λ) implies that H≅GH≅G. In this paper, we shall determine all chromatic equivalence classes of 2-connected (n,n+4)(n,n+4)-graphs with three triangles and one induced 4-cycle, under the equivalence relation ‘ ∼’. As a by product of these, we obtain various new families of chromatically-equivalent graphs and chromatically-unique graphs.

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