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
    0 references
    0 references
    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
    0 references
    forbidden subgraphs
    0 references
    2-factors
    0 references
    Hamiltonian
    0 references
    0 references