Chromaticity of series-parallel graphs (Q1918563)

If \(P(G, \lambda)\) denotes the chromatic polynomial of a graph \(G\), two graphs \(G\) and \(H\) are said to be \(\chi\)-equivalent, written \(G \sim H\), if \(P(G, \lambda) = P (H, \lambda)\). Any equivalence class induced by \(\sim\) is called a \(\chi\)-equivalence class. A \(k\)-gon tree is obtained by edge-gluing a set of cycles each of order \(k\) successively. A graph is called a generalised polygon tree if it is a subdivision of a \(k\)-gon tree. Alternatively, a generalised polygon tree can be viewed as a 2-connected simple series-parallel graph (sp graph). In this paper some new chromatic invariants for sp graphs are introduced and it is proved that the class of polygon trees is a \(\chi\)-equivalence class. A class of sp graphs, called \(\Theta_k\)-gons, is shown to be closed under \(\chi\)-equivalence and some classes of \(\Theta_k\)-gons are identified to possess the same property; one of them is the class of \(k\)-gon trees.