Chromatic Classes of 2-Connected (n,n+4)‎-Graphs with Exactly Three Triangles and at Least Two Induced 4-Cycles

Abstract EN

For a graph G, let P(G,λ) be its chromatic polynomial.

Two graphs G and H are chromatically equivalent, denoted G∼H, if P(G,λ)=P(H,λ).

A graph G is chromatically unique if P(H,λ)=P(G,λ) implies that H≅G.

In this paper, we determine all chromatic equivalence classes of 2-connected (n,n+4)-graphs with exactly three triangles and at least two induced 4-cycles.

As a byproduct of these, we obtain various new families of χ-equivalent graphs and χ-unique graphs.