Forbidden subgraphs and 2-factors in 3/2-tough graphs

2021/10/04 by Masahiro Sanka, Sanka, Masahiro
Computer Science · Mathematics · #05C38 #05C42 #05C45 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2110.01281

openalex publication_date 2021/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A graph G is H-free if it has no induced subgraph isomorphic to H, where H is a graph. In this paper, we show that every (3)/(2)-tough (P₄ ∪ P₁₀)-free graph has a 2-factor. The toughness condition of this result is sharp. Moreover, for any ε>0 there exists a (2-ε)-tough 2P₅-free graph without a 2-factor. This implies that the graph P₄ ∪ P₁₀ is best possible for a forbidden subgraph in a sense.

Related

• Existence of 2-Factors in Tough Graphs without Forbidden Subgraphs
• Toughness and existence of 2-factors
• 2-factors in (3)/(2)-tough maximal planar graphs
• Hamiltonian cycles in 3-tough 2K₂-free graphs
• Hamiltonian cycles in 2-tough 2K₂-free graphs