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

  • Christopher Carl Heckman
  • Roi Krakovski
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