# 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.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text: