Characterizing the Difference Between Graph Classes Defined by Forbidden Pairs Including the Claw

For two graphs A and B, a graph G is called {A, B}-free if G contains neither A nor B as an induced subgraph. Let Pn denote the path of order n. For nonnegative integers k, andm, let Nk, ,m be the graph obtained from K3 and three vertex-disjoint paths Pk+1, P +1, Pm+ 1 by identifying each of the vertices of K3 with one endvertex of one of the paths. Let Zk = Nk, 0,0 and Bk, = Nk, ,0. Bedrossian characterized all pairs {A, B} of connected graphs such that every 2-connected {A, B}-free graph is Hamiltonian. All pairs appearing in the characterization involve the claw ( K1,3) and one of N1,1,1, P6 and B1,2. In this paper, we characterize connected graphs that are (i) {K1,3, Z2}free but not B1,1-free, (ii) {K1,3, B1,1}-free but not P5-free, or (iii) {K1,3, B1,2}-free but not P6-free. The third result is closely related to Bedrossian's characterization. Furthermore, we apply our characterizations to some forbidden pair problems.