A Pair of Forbidden Subgraphs and 2-Factors
Jun Fujisawa, Akira Saito · Combinatorics Probability Computing · 2012
In this paper, we consider pairs of forbidden subgraphs that imply the existence of a 2-factor in a graph. Ford≥ 2, let dbe the set of connected graphs of minimum degree at leastd. LetF1andF2be connected graphs and let be a set of connected graphs. Then {F1,F2} is said to be a forbidden pair for if every {F1,F2}-free graph in of sufficiently large order has a 2-factor. Faudree, Faudree and Ryjáček have characterized all the forbidden pairs for the set of 2-connected graphs. We first characterize the forbidden pairs for 2, which is a larger set than the set of 2-connected graphs, and observe a sharp difference between the characterized pairs and those obtained by Faudree, Faudree and Ryjáček. We then consider the forbidden pairs for connected graphs of large minimum degree. We prove that if {F1,F2} is a forbidden pair for d, then eitherF1orF2is a star of order at mostd+ 2. Ota and Tokuda have proved that every $K_{1, \lfloor\frac{d+2}{2}\rfloor}$ -free graph of minimum degree at leastdhas a 2-factor. These results imply that fork≥d+ 2, no connected graphsFexcept for stars of order at mostd+ 2 make {K1,k,F} a forbidden pair for d, while for $k\le \bigl\lfloor\frac{d+2}{2} \bigr\rfloor$ every connected graphFmakes {K1,k,F} a forbidden pair for d. We consider the remaining range of $\bigl\lfloor\frac{d+2}{2} \bigr\rfloor < k < d+2$ , and prove that only a finite number of connected graphsFmake {K1,k,F} a forbidden pair for d.