Erdős-Gyárfás conjecture for cubic planar graphs (Q1953482)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Erdős-Gyárfás conjecture for cubic planar graphs |
scientific article |
Statements
Erdős-Gyárfás conjecture for cubic planar graphs (English)
0 references
7 June 2013
0 references
Summary: In 1995, \textit{P. Erdős} and \textit{A. Gyárfás} [Math. Pannonica 6, No. 1, 7--10 (1995; Zbl 0828.05040)] 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.
0 references
Erdős-gyárfás conjecture
0 references
cycles of prescribed lengths
0 references
cubic planar graphs
0 references