zbMATH — the first resource for mathematics

Chromatically equivalent graphs. (English) Zbl 0665.05018
Vertex colourings of graphs with the property that no two adjacent vertices have the same colour are considered. Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial, and a graph is chromatically unique if it is completely determined (up to isomorphism) by its chromatic polynomial.
In the paper chromatic polynomials of graphs called supercycles and of graphs associated to them are determined. A supercycle \(C=C(s_ 1,s_ 2,...,s_ k)\) is a graph obtained from a cycle with vertices \(P_ 1,P_ 2,...,P_ v\) by adding a new vertex \(P_ 0\) and the edges \(P_ 0P_ 1,P_ 0P_{s_ 1+1},P_ 0P_{s_ 1+s_ 2+1},...,P_ 0P_{s_ 1+s_ 2+...+s_{k-1}+1}\), where \(v=s_ 1+s_ 2+...+s_ k.\)
Further it is proved that the supercycles C(s,s), C(1,s,s) and C(1,s-1,s) are chromatically unique. There are results concerning chromatically equivalent graphs as the following: If the graph G has only t s-cycles and G’ is chromatically equivalent to G then G’ has t s-cycles and no smaller cycles.
Reviewer: U.Baumann

05C15 Coloring of graphs and hypergraphs