zbMATH — the first resource for mathematics

On trees of polygons. (English) Zbl 0575.05027
The set S of n-gon-trees is defined recursively as follows: (a) The n-gon is in S. (b) If G is in S, then so is any graph formed by identifying an edge of G with an edge of an n-gon. The authors prove that a graph is an n-gon-tree on k n-gons if and only if its chromatic polynomial is $[(\lambda -1)^ n+(-1)^ n(\lambda -1)]^ k/[\lambda (\lambda - 1)]^{k-1}.$ [Reviewer’s comments: The elaborate definition of $$Q(C_ n,\lambda)$$ in Lemma 5 is unnecessary. Corollary 1.1 is a result due to G. H. J. Meredith [J. Comb. Theory, Ser. B 13, 14-17 (1972; Zbl 0218.05056)].]