zbMATH — the first resource for mathematics

Classes of chromatically equivalent graphs and polygon trees. (English) Zbl 0813.05030
If two graphs $$G$$ and $$H$$ have the same chromatic polynomial, i.e. $$P(G,\lambda)= P(H, \lambda)$$, we say that $$G$$ and $$H$$ are chromatically equivalent. If $$P(G, \lambda)= P(H, \lambda)$$ implies that $$H$$ is isomorphic to $$G$$, we say that $$G$$ is chromatically unique. The author gives definitions of maximal classes of chromatically equivalent graphs and complete classes of chromatically equivalent graphs and investigates their properties. In particular, he studies graphs which contain no subgraph homeomorphic to $$K_ 4$$ and shows that they are just generalized polygon trees.
Next, he defines the notion of intercourse number of a generalized polygon tree and shows that this is an invariant of such a graph under chromatic equivalence. This result is very useful in the study of chromatically equivalent graphs. As a consequence, the author shows that $$\{\{C_{i_ 0},\dots, C_{i_ k}\}, k\{K_ 2\}\}$$ is a complete class of chromatically equivalent graphs, which solves a problem raised by Whitehead Jr. in 1988.
Reviewer: M.Kubale (Gdańsk)

MSC:
 05C15 Coloring of graphs and hypergraphs 05C05 Trees 05C75 Structural characterization of families of graphs
Full Text:
References:
 [1] Chao, C.Y.; Li, N.Z., On trees of polygons, Arch. math., 45, 180-185, (1985) · Zbl 0575.05027 [2] Chao, C.Y.; Li, N.Z.; Xu, S.J., On q-trees, J. graph theory, 10, 129-136, (1986) · Zbl 0591.05021 [3] Chao, C.Y.; Whitehead, E.G., On chromatic equivalence of graphs, (), 121-131 [4] Chao, C.Y.; Zhao, L.C., Chromatic polynomials of a family of graphs, Ars combin., 15, 111-129, (1983) · Zbl 0532.05027 [5] Koh, K.M.; Teo, K.L., The search for chromatically unique graphs, Graphs combin., 6, 259-285, (1990) · Zbl 0727.05023 [6] Read, R.C., An introduction to chromatic polynomials, J. combin., 4, 52-71, (1968) · Zbl 0173.26203 [7] Whitehead, E.G., Chromaticity of 2-trees, J. graph theory, 9, 279-284, (1985) · Zbl 0574.05016 [8] Whitehead, E.G., Chromatic polynomials of generalized trees, Discrete math., 72, 391-393, (1988) · Zbl 0659.05045 [9] Whitehead, E.G.; Zhao, L.C., Cutpoints and the chromatic polynomial, J. graph theory, 8, 371-377, (1984) · Zbl 0551.05041 [10] Xu, S.J.; Li, N.Z., The chromaticity of wheels, Discrete math., 51, 207-212, (1984) · Zbl 0547.05032
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.