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

Abstract

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, $\ell$ and m, let $N_{k,\ell ,m}$ be the graph obtained from $K_{3}$ and three vertex-disjoint paths $P_{k+1}$, $P_{\ell +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,\ell }=N_{k,\ell ,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.