Chromatic polynomials, polygon trees, and outerplanar graphs. (English) Zbl 0778.05074

Summary: It is proved that all classes of polygon trees are characterized by their chromatic polynomials, and a characterization is given of those polynomials that are chromatic polynomials of outerplanar graphs. The first result yields an alternative proof that outerplanar graphs are recognizable from their vertex-deleted subgraphs.


05C75 Structural characterization of families of graphs
05C05 Trees
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Chao, Arch. Math. 45 pp 180– (1985)
[2] Chao, Arch. Math. 43 pp 187– (1984)
[3] Giles, J. Combinat. Theory B 16 pp 215– (1974)
[4] All the king’s horses. Graph Theory and Related Topics. Academic Press, New York (1979), 15–33.
[5] Woodall, Discrete Math. 101 (1992)
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.