1School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ 85287 - 1804 2Department of Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel
The electronic journal of combinatorics, Tome 20 (2013) no. 2
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.
1
School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ 85287 - 1804
2
Department of Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel
@article{10_37236_3252,
author = {Christopher Carl Heckman and Roi Krakovski},
title = {Erd\H{o}s-Gy\'arf\'as conjecture for cubic planar graphs},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {2},
doi = {10.37236/3252},
zbl = {1267.05152},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3252/}
}
TY - JOUR
AU - Christopher Carl Heckman
AU - Roi Krakovski
TI - Erdős-Gyárfás conjecture for cubic planar graphs
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/3252/
DO - 10.37236/3252
ID - 10_37236_3252
ER -
%0 Journal Article
%A Christopher Carl Heckman
%A Roi Krakovski
%T Erdős-Gyárfás conjecture for cubic planar graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3252/
%R 10.37236/3252
%F 10_37236_3252
Christopher Carl Heckman; Roi Krakovski. Erdős-Gyárfás conjecture for cubic planar graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/3252
