Erdős-Gyárfás conjecture for cubic planar graphs
type: Item
instance of: scholarly article
title: Erdős-Gyárfás conjecture for cubic planar graphs
zbMATH Open document ID: 1267.05152
author: Christopher Carl Heckman
author: Roi Krakovski
published in: The Electronic Journal of Combinatorics
publication date: 2013-06-07T00:00:00Z
full work available at URL: v20i2p7
review text: 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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 6171922
zbMATH Keywords: Erdős-gyárfás conjecture
zbMATH Keywords: cycles of prescribed lengths
zbMATH Keywords: cubic planar graphs
MaRDI profile type: Publication
cites work: Some old and new problems in various branches of combinatorics
cites work: Q4329122
description: scientific article; zbMATH DE number 6171922