Pósa's conjecture for graphs of order at least 2 × 108

DOI10.1002/RSA.20376MaRDI QIDQ5388972zbMATH OpenOpenAlexWikidataFDO

Authors Phong Châu, Louis DeBiasio, H. A. Kierstead

Publication date 24 April 2012

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

powers of cyclesPósa's Conjecturesquare cycle

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

Abstract: In 1962 P'osa conjectured that every graph G on n vertices with minimum degree at least 2n/3 contains the square of a hamiltonian cycle. In 1996 Fan and Kierstead proved the path version of P'osa's Conjecture. They also proved that it would suffice to show that G contains the square of a cycle of length greater than 2n/3. Still in 1996, Koml'os, S'ark"ozy, and Szemer'edi proved P'osa's Conjecture, using the Regularity and Blow-up Lemmas, for graphs of order n > n_0, where n_0 is a very large constant. Here we show without using these lemmas that n_0=2 imes 10^8 is sufficient. We are motivated by the recent work of Levitt, Szemer'edi and S'ark"ozy, but our methods are based on techniques that were available in the 90's.

Recommendations

• scientific article; zbMATH DE number 2170333
• On Pósa's conjecture for random graphs
• Erdős-Gyárfás conjecture for \(P_8\)-free graphs
• The Kuratowski covering conjecture for graphs of order < 10 for the nonorientable surfaces of genus 3 and 4
• scientific article; zbMATH DE number 7157680
• ON A CONJECTURE ONnTH ORDER DEGREE REGULAR GRAPHS
• The ^2 conjecture holds for graphs of small order
• De Bruijn-Erdős-type theorems for graphs and posets
• Enomoto and Ota's conjecture holds for large graphs
• The Erdős-Pósa property for odd cycles in graphs of large connectivity

Cites work

• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A note on some embedding problems for oriented graphs
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Blow-up lemma
• Graph theory
• Hamiltonian square-paths
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• scientific article; zbMATH DE number 1286511 (Why is no real title available?)
• On the square of a Hamiltonian cycle in dense graphs
• Partitioning a graph into two square-cycles
• Proof of the Seymour conjecture for large graphs
• Some Theorems on Abstract Graphs
• The square of paths and cycles

Cited in

(21)

• Square Hamiltonian cycles in graphs with maximal 4-cliques
• Monochromatic square-cycle and square-path partitions
• Monochromatic cycle power partitions
• Stability for vertex cycle covers
• On prisms, Möbius ladders and the cycle space of dense graphs
• Triangle resilience of the square of a Hamilton cycle in random graphs
• Ramsey number of a connected triangle matching
• On degree sequences forcing the square of a Hamilton cycle
• Filling the gap between Turán's theorem and Pósa's conjecture
• On a degree sequence analogue of Pósa's conjecture
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• An Ore-type theorem on Hamiltonian square cycles
• Hamiltonian cycles with all small even chords
• On Pósa's conjecture for random graphs
• Monochromatic bounded degree subgraph partitions
• Minimum Degrees for Powers of Paths and Cycles
• Ore-degree threshold for the square of a Hamiltonian cycle
• The critical window for the classical Ramsey-Turán problem
• Covering cycles in sparse graphs
• Characterizing forbidden pairs for Hamiltonian squares
• How to avoid using the regularity Lemma: Pósa's conjecture revisited

This page was built for publication: Pósa's conjecture for graphs of order at least 2 × 10⁸

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