# zbMATH — the first resource for mathematics

On the chromatic uniqueness of certain trees of polygons. (English) Zbl 0795.05060
Let $$m$$ and $$n_ 1, \dots, n_ m$$ be integers satisfying $$m\geq 1$$ and $$n_ m > \cdots > n_ 2 > n_ 1 \geq 3$$. Let $${\mathcal G}$$ be the class of graphs defined recursively by the following rules: the $$n_ i$$-cycle is in $${\mathcal G}$$ for each $$i=1,\dots,m$$ and if $$G_ 1$$ and $$G_ 2$$ belong to $${\mathcal G}$$ then so does any graph that can be formed from $$G_ 1$$ and $$G_ 2$$ by identifying an edge of $$G_ 1$$ with an edge of $$G_ 2$$. The graphs in $${\mathcal G}$$ are called $$(n_ 1, \dots, n_ m)$$-gon-trees or simply trees of polygons. If $$m=1$$ and $$n_ 1=n$$ then the graphs in $${\mathcal G}$$ are called $$n$$-gon-trees. A characterization of $$n$$-gon-trees was given by C. Chao and N. Li [Arch. Math. 45, 180-185 (1985; Zbl 0575.05027)]. In this paper the author establishes a characterization of certain trees of polygons satisfying $$n_ m \leq n_ 1+ \lfloor (n_ 1-3)/2 \rfloor$$.
Reviewer: M.Kubale (Gdańsk)

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C75 Structural characterization of families of graphs