Chromatic classes of 2-connected (n, n + 3)-graphs with at least two triangles

Abstract

Let P(G) denote the chromatic polynomial of a graph G. Two graphs G and H are chromatically equivalent, written G ∼ H, if P(G) = P(H). A graph G is chromatically unique if G ≅ H for any graph H such that H ∼ G. Let H denote the class of 2-connected graphs with n vertices and n + 3 edges which contain at least two triangles. It follows that if G ε{lunate} H and H ∼ G, then H ε{lunate} H. In this paper, we determine all equivalence classes in H under the equivalence relation ∼ and characterize the structure of the graphs in each class. As a by-product of these, we obtain various new families of chromatically equivalent graphs and chromatically unique graphs. © 1994.