A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture

DOI10.1016/J.JCTB.2020.08.003zbMATH Open1457.05057arXiv2002.04198OpenAlexW3104754894MaRDI QIDQ2221920FDOQ2221920

Authors: Bo Ning, Binlong Li 

Publication date: 3 February 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: For a 2-connected graph $G$ on $n$ vertices and two vertices $x,yinV(G)$, we prove that there is an $(x,y)$-path of length at least $k$ if there are at least $fracn-12$ vertices in $$ of degree at least $k$. This strengthens a well-known theorem due to ErdH{o}s and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with $n$ vertices contains a cycle of length at least $2k$ if it has at least $fracn2+k$ vertices of degree at least $k$. This confirms a 1975 conjecture made by Woodall. As another applications, we obtain some results which generalize previous theorems of Dirac, ErdH{o}s-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Koml'{o}s-S'{o}s Conjecture which was verified by Bazgan et al. and of a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond.

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

Recommendations

• A proof of the Erdös-Sands-Sauer-Woodrow conjecture
• On Erdős-Wood's conjecture
• A strengthening of the Erdős-Szekeres theorem
• Proof of a conjecture of Bollobás and Kohayakawa on the Erdős-Stone theorem
• scientific article; zbMATH DE number 4014774
• A survey and strengthening of Erdős-Gyarfas conjecture
• scientific article; zbMATH DE number 4213130
• On stronger conjectures that imply the Erdős-Moser conjecture
• A note on a theorem of Erdős and Gallai
• scientific article; zbMATH DE number 5224778

zbMATH Keywords

Woodall's conjecturelong cycleFan lemmaErdős-Gallai theorem

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Cites Work

• On graphs with randomly deleted edges
• On maximal paths and circuits of graphs
• On the Loebl-Koml�s-S�s conjecture
• Title not available (Why is that?)
• Graph theory with applications
• Title not available (Why is that?)
• Some Theorems on Abstract Graphs
• Subgraph coverings and edge switchings
• Title not available (Why is that?)
• Large cycles in graphs
• Title not available (Why is that?)
• On a conjecture of Bondy
• On a conjecture of Woodall
• Title not available (Why is that?)
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• Title not available (Why is that?)
• A degree condition for the circumference of a graph
• The longest cycle of a graph with a large minimal degree
• Title not available (Why is that?)
• Relative lengths of paths and cycles in k-connected graphs
• Stability results on the circumference of a graph
• Heavy cycles passing through some specified vertices in weighted graphs
• Title not available (Why is that?)

Cited In (11)

• A stability result of the Pósa lemma
• Cycles in 2-connected graphs
• On a conjecture of Woodall
• Proof of a conjecture of Bollobás and Kohayakawa on the Erdős-Stone theorem
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• A survey and strengthening of Erdős-Gyarfas conjecture
• Stability in the Erdős-Gallai theorems on cycles and paths
• Stability version of Dirac's theorem and its applications for generalized Turán problems
• A unified simple proof of a conjecture of Woods for \(n\leq 6\)
• Title not available (Why is that?)
• Erdős-Gallai stability theorem for linear forests

This page was built for publication: A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture

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