Erdös-Gyárfás Conjecture for Cubic Planar Graphs

  • Christopher Carl Heckman School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ 85287 - 1804
  • Roi Krakovski Department of Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel
Keywords: Erdös-Gyárfás Conjecture, Cycles of prescribed lengths, Cubic planar graphs


In 1995, Paul Erdös and András Gyárfás conjectured that for every graph of minimum degree at least 3, there exists a non-negative integer $m$ such that $G$ contains a simple cycle of length $2^m$. In this paper, we prove that the conjecture holds for 3-connected cubic planar graphs. The proof is long, computer-based in parts, and employs the Discharging Method in a novel way.
Article Number