On the chromatic equivalence class of graphs (Q1377862): Difference between revisions

Let \(P(G, \lambda)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent if \(P(G,\lambda) = P(H,\lambda)\). The chromatic equivalence class of \(G\) consists of all graphs chromatically equivalent to \(G\). For example, the chromatic equivalence class of a tree consists of exactly all other trees of the same order. The join of two graphs \(G\) and \(H\) is obtained by taking a disjoint copy of each graph and adding edges from every vertex of \(G\) to every vertex of \(H\). The author determines the class of all graphs in the chromatic equivalence class of the join of \(m\) copies of paths each of length 3. He also gives two operations, which when applied to graphs in the chromatic equivalence class of \(G\), give all graphs with chromatic polynomial \(\lambda P(G,\lambda)\). A similar result is given for all graphs with chromatic polynomial \((\lambda -1) P(G,\lambda)\).