×

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
PDF BibTeX XML Cite