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

DOI10.1002/JGT.22916zbMATH Open1522.05318arXiv2110.01281OpenAlexW3202435412MaRDI QIDQ6074577FDOQ6074577

Authors:

Publication date: 12 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

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 $frac32$-tough $(P_{4}cup{P}_{10})$-free graph has a 2-factor. The toughness condition of this result is sharp. Moreover, for any $varepsilon>0$ there exists a $(2-varepsilon)$-tough $2P_5$-free graph without a 2-factor. This implies that the graph $P_{4}cup{P}_{10}$ is best possible for a forbidden subgraph in a sense.

Full work available at URL: https://arxiv.org/abs/2110.01281

Recommendations

• Existence of 2-factors in tough graphs without forbidden subgraphs
• Forbidden subgraphs and the existence of a 2-factor
• Forbidden subgraphs for existences of (connected) 2-factors of a graph
• scientific article; zbMATH DE number 1743771
• Two forbidden subgraphs and the existence of a 2-factor in graphs
• Forbidden subgraphs that imply 2-factors
• Pairs and triples of forbidden subgraphs and the existence of a 2-factor
• Forbidden subgraphs that imply 2-factors with a specified number of components
• Toughness, forbidden subgraphs and pancyclicity
• A pair of forbidden subgraphs and 2-factors

zbMATH Keywords

Hamiltonian cycle2-factortoughness\((P_4 \cup P_{10})\)-free graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Title not available (Why is that?)
• Graph theory
• Toughness, hamiltonicity and split graphs
• Not every 2-tough graph is Hamiltonian
• Toughness in graphs -- a survey
• Tough graphs and Hamiltonian circuits.
• The Factors of Graphs
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• 10-tough chordal graphs are Hamiltonian
• Toughness and the existence ofk-factors
• Chordality and 2-factors in tough graphs
• Tough spiders
• Toughness, minimum degree, and the existence of 2‐factors
• Vizing's 2-factor conjecture involving toughness and maximum degree conditions
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs

Cited In (4)

• Toughness, forbidden subgraphs and pancyclicity
• Existence of 2-factors in tough graphs without forbidden subgraphs
• Chordality and 2-factors in tough graphs
• A pair of forbidden subgraphs and 2-factors

This page was built for publication: Forbidden subgraphs and 2‐factors in 3/2‐tough graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074577)