Planar graphs without cycles of specific lengths (Q697075)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Planar graphs without cycles of specific lengths |
scientific article |
Statements
Planar graphs without cycles of specific lengths (English)
0 references
12 September 2002
0 references
\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.
0 references
list colouring
0 references
planar graph
0 references
cycle
0 references