Forbidden subgraphs that imply 2-factors (Q2477381)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Forbidden subgraphs that imply 2-factors |
scientific article |
Statements
Forbidden subgraphs that imply 2-factors (English)
0 references
13 March 2008
0 references
The main result of this paper is a characterization of connected forbidden subgraphs and pairs of connected forbidden subgraphs that imply that a 2-connected graph \(G\) has a 2-factor. The characterization includes, in addition to forbidden pairs implying Hamiltonicity, see [\textit{R. J. Faudree} and \textit{R. J. Gould}, ``Characterizing forbidden pairs for hamiltonian properties'', Discrete Math. 173, No. 1--3, 45--60 (1997; Zbl 0879.05050)], six pairs containing the claw as well as the pair \((K_{1,4} , P_4)\). An important concept used in the proof is the \textit{Z. Ryjáček} closure for claw free graphs introduced in [``On a closure concept in claw-free graphs'', J. Comb. Theory, Ser. B 70, No. 2, 217--224 (1997; Zbl 0872.05032)].
0 references
forbidden subgraphs
0 references
2-factors
0 references
Hamiltonian
0 references