10-tough chordal graphs are Hamiltonian

2015/08/11 by Kabela, Adam, Kaiser, Tomáš
#05C42 #05C45 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1508.02568

Abstract

Chen et al. proved that every 18-tough chordal graph has a Hamilton cycle [Networks 31 (1998), 29-38]. Improving upon their bound, we show that every 10-tough chordal graph is Hamiltonian (in fact, Hamilton-connected). We use Aharoni and Haxell's hypergraph extension of Hall's Theorem as our main tool.

Related

• A Note on Hamilton Cycles
• Hamiltonian cycles in 7-tough (P₄∪ P₁)-free graphs
• Cycle Extendability of Hamiltonian Strongly Chordal Graphs
• Hamilton cycles in tough (2P₂ ∪ P₁)-free graphs
• Degree Sequence Condition for Hamiltonicity in Tough Graphs