Classes of chromatically equivalent graphs and polygon trees (Q1336708)

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.