Planar graphs without cycles of specific lengths
type: Item
instance of: scholarly article
title: Planar graphs without cycles of specific lengths
zbMATH Open document ID: 1001.05042
published in: European Journal of Combinatorics
publication date: 2002-09-12T00:00:00Z
review text: \textit{W. Weifan} and \textit{K.-W. Lih} [Appl. Math. Lett. 15, 561-565 (2002; Zbl 0994.05060)] proved that planar graphs without 5-cycles are 3-degenerate and conjectured [Comb. Probab. Comput. 10, 267-276 (2001; Zbl 0982.05046)] that the same holds for planar graphs without 6-cycles. In the paper under review, this conjecture is proved; combined with the result of \textit{P. C. B. Lam, B. Xu} and \textit{J. Liu} [J. Comb. Theory, Ser. B 76, 117-126 (1999; Zbl 0931.05036)] it implies that every planar graph without \(k\)-cycles, \(3 \leq k \leq 6\), is 4-choosable. The proof is based on the discharging method.
reviewed by: Tomáš Madaras
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1800367
zbMATH Keywords: list colouring
zbMATH Keywords: planar graph
zbMATH Keywords: cycle
author: Gašper Fijavž
author: Martin Juvan
author: Bojan Mohar
author: Riste Škrekovski
MaRDI profile type: Publication
OpenAlex ID: W2068409559
cites work: Q3142409
cites work: The complexity of planar graph choosability
cites work: 25 pretty graph colouring problems
cites work: Q4263476
cites work: The 4-choosability of plane graphs without 4-cycles
cites work: Q4882549
cites work: Every planar graph is 5-choosable
cites work: 3-list-coloring planar graphs of girth 5
cites work: Graph colorings with local constraints -- a survey
cites work: List colourings of planar graphs
cites work: A not 3-choosable planar graph without 3-cycles
cites work: Choosability and edge choosability of planar graphs without five cycles
cites work: Structural properties and edge choosability of planar graphs without 6-cycles
DOI: 10.1006/EUJC.2002.0570
description: scientific article; zbMATH DE number 1800367