×

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)].]
Reviewer: R.C.Read

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] C.-Y.Chao and E. G.Whitehead, Jr., On chromatic equivalence of graphs, Theory and Applications of Graphs. Eds: Y. Alavi and D. R. Lick; LNM642, 121-131, Berlin-Heidelberg-New York 1978.
[2] C.-Y. Chao andL.-C. Zhao, Chromatic polynomials of connected graphs. Arch. Math.43, 187-192 (1984). · Zbl 0535.05053 · doi:10.1007/BF01193920
[3] E. J. Farrell, On chromatic coefficients. Discrete Math.4, 257-264 (1980). · Zbl 0443.05041 · doi:10.1016/0012-365X(80)90154-5
[4] K. Kuratowski, Sur le problem des courbes gauches en topologie. Fund. Math.16, 271-283 (1930). · JFM 56.1141.03
[5] R. C. Read, An introduction to chromatic polynomials. J. Combin. Theory4, 52-71 (1968). · Zbl 0173.26203 · doi:10.1016/S0021-9800(68)80087-0
[6] E. G.Whitehead, Jr., Chromaticity of two-trees. To appear in J. Graph Theory.
[7] H. Whitney, The coloring of graphs. Ann. of Math.33, 688-718 (1932). · JFM 58.0606.01 · doi:10.2307/1968214
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.