Erdös-Gyárfás Conjecture for Cubic Planar Graphs
Christopher Heckman, Roi Krakovski · The Electronic Journal of Combinatorics · 2013
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.