How to avoid using the regularity Lemma: Pósa's conjecture revisited

DOI10.1016/j.disc.2009.05.020zbMath1188.05080OpenAlexW2063579746WikidataQ123027131 ScholiaQ123027131MaRDI QIDQ960978

Ian Levitt, Endre Szemerédi, Gábor N. Sárközy

Publication date: 29 March 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2009.05.020

zbMATH Keywords

square of Hamilton cyclePósa conjectureextremal embedding problemsRegularity Lemma

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42)

Related Items

Monochromatic cycle power partitions, On a degree sequence analogue of Pósa's conjecture, Distributing pairs of vertices on Hamiltonian cycles, Monochromatic cycle partitions of graphs with large minimum degree, An Ore-type theorem on Hamiltonian square cycles, Stability for vertex cycle covers, Triangle resilience of the square of a Hamilton cycle in random graphs, On directed versions of the Corrádi-Hajnal corollary, Covering cycles in sparse graphs, Hamiltonian cycles with all small even chords, Characterizing forbidden pairs for Hamiltonian squares, A general approach to transversal versions of Dirac‐type theorems, On multipartite Hajnal-Szemerédi theorems, An Extension of the Hajnal–Szemerédi Theorem to Directed Graphs, Semi-degree threshold for anti-directed Hamiltonian cycles, On Degree Sequences Forcing The Square of a Hamilton Cycle, Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs, Pósa's conjecture for graphs of order at least 2 × 10⁸, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Monochromatic cycle partitions of \(2\)-coloured graphs with minimum degree \(3n/4\), Monochromatic bounded degree subgraph partitions, The critical window for the classical Ramsey-Turán problem, Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs, Ramsey Number of a Connected Triangle Matching, Monochromatic square-cycle and square-path partitions, Stability of the path-path Ramsey number, Spectral radius and the 2-power of Hamilton cycle, The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs

Cites Work

• Proof of the Seymour conjecture for large graphs
• Blow-up lemma
• Square Hamiltonian cycles in graphs with maximal 4-cliques
• The square of paths and cycles
• Hamiltonian square-paths
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• An algorithmic version of the blow-up lemma
• The Square of a Hamiltonian Cycle
• Partitioning a graph into two square-cycles
• On the square of a Hamiltonian cycle in dense graphs
• Some Theorems on Abstract Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item