zbMATH — the first resource for mathematics

Chromatic equivalence classes of certain cycles with edges. (English) Zbl 0971.05040
Let \(P(G)\) denote the chromatic polynomial of a graph \(G\). A graph \(G\) is said to be chromatically unique if for any graph \(H\), \(P(G)=P(H)\) implies that \(G\) is isomorphic with \(H\). A path in \(G\) is called a simple path if the degree of each interior vertex is two in \(G\). A generalized polygon tree is a graph defined recursively as follows: A cycle \(C_{p}\) \((p\geq 3)\) is a generalized polygon tree. Next, suppose \(H\) is a generalized polygon tree containing a simple path \(P_{k}\), where \(k\geq 1\). If \(G\) is a graph obtained from the union of \(H\) and a cycle \(C_{r}\), where \(r>k\), by identifying \(P_{k}\) in \(H\) with a path of length \(k\) in \(C_{r}\), then \(G\) is also a generalized polygon tree.
In this paper necessary and sufficient conditions for a family of generalized polygon trees to be chromatically unique are given.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI