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

DOI10.1016/J.JCTB.2020.08.003MaRDI QIDQ2221920zbMATH OpenOpenAlexFDO

Authors Bo Ning, Binlong Li

Publication date 3 February 2021

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

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

zbMATH Keywords

Woodall's conjecturelong cycleFan lemmaErdős-Gallai theorem

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3914359 (Why is no real title available?)
• scientific article; zbMATH DE number 3929041 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3733966 (Why is no real title available?)
• scientific article; zbMATH DE number 3515497 (Why is no real title available?)
• scientific article; zbMATH DE number 3561382 (Why is no real title available?)
• scientific article; zbMATH DE number 205838 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• A degree condition for the circumference of a graph
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• Graph theory with applications
• Heavy cycles passing through some specified vertices in weighted graphs
• Large cycles in graphs
• On a conjecture of Bondy
• On a conjecture of Woodall
• On graphs with randomly deleted edges
• On maximal paths and circuits of graphs
• On the Loebl-Koml�s-S�s conjecture
• Relative lengths of paths and cycles in k-connected graphs
• Some Theorems on Abstract Graphs
• Stability results on the circumference of a graph
• Subgraph coverings and edge switchings
• The longest cycle of a graph with a large minimal degree

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
• A unified simple proof of a conjecture of Woods for \(n\leq 6\)
• Stability version of Dirac's theorem and its applications for generalized Turán problems
• scientific article; zbMATH DE number 3914359 (Why is no real title available?)
• 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)