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 P n denote the path of order n. For nonnegative integers k, ℓ and m, let N k , ℓ , m be the graph obtained from K 3 and three vertex-disjoint paths P k + 1 , P ℓ + 1 , P m + 1 by identifying each of the vertices of K 3 with one endvertex of one of the paths. Let Z k = N k , 0 , 0 and B k , ℓ = N k , ℓ , 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 ( K 1 , 3 ) and one of N 1 , 1 , 1 , P 6 and B 1 , 2 . In this paper, we characterize connected graphs that are (i) { K 1 , 3 , Z 2 } -free but not B 1 , 1 -free, (ii) { K 1 , 3 , B 1 , 1 } -free but not P 5 -free, or (iii) { K 1 , 3 , B 1 , 2 } -free but not P 6 -free. The third result is closely related to Bedrossian's characterization. Furthermore, we apply our characterizations to some forbidden pair problems. [ABSTRACT FROM AUTHOR]