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

Phong Châu, Louis Debiasio, Henry Kierstead

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


In 1962 Pósa conjectured that every graph G on n vertices with minimum degree contains the square of a hamiltonian cycle. In 1996 Fan and Kierstead proved the path version of Pósa's Conjecture. They also proved that it would suffice to show that G contains the square of a cycle of length greater than. Still in 1996, Komlós, Sárközy, and Szemerédi proved Pósa's Conjecture, using the Regularity and Blow-up Lemmas, for graphs of order n ≥ n0, where n0 is a very large constant. Here we show without using these lemmas that n0:= 2 × 108 is sufficient. We are motivated by the recent work of Levitt, Sárközy and Szemerédi, but our methods are based on techniques that were available in the 90's.

Original languageEnglish (US)
Pages (from-to)507-525
Number of pages19
JournalRandom Structures and Algorithms
Issue number4
StatePublished - Dec 2011


  • Powers of cycles
  • Pósa's Conjecture
  • Square cycle

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Pósa's conjecture for graphs of order at least 2 × 108'. Together they form a unique fingerprint.

Cite this