Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651176 | Discrete Mathematics | 2006 | 8 Pages |
Abstract
For a graph G , let P(G)P(G) be its chromatic polynomial. Two graphs G and H are chromatically equivalent if P(G)=P(H)P(G)=P(H). A graph G is chromatically unique if P(H)=P(G)P(H)=P(G) implies that H≅GH≅G. In this paper, we classify the chromatic classes of graphs obtained from K2,2,2∪Pm(m⩾3)K2,2,2∪Pm(m⩾3), (K2,2,2-e)∪Pm(m⩾5)(K2,2,2-e)∪Pm(m⩾5) and (K2,2,2-2e)∪Pm(m⩾6)(K2,2,2-2e)∪Pm(m⩾6) by identifying the end-vertices of the path PmPm with any two vertices of K2,2,2K2,2,2, K2,2,2-eK2,2,2-e and K2,2,2-2eK2,2,2-2e, respectively, where e and 2e2e are, respectively, an edge and any two edges of K2,2,2K2,2,2. As a by-product of this, we obtain some families of chromatically unique and chromatically equivalent classes of graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
G.C. Lau, Y.H. Peng,