Planar graphs without cycles of specific lengths
\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.
scientific article; zbMATH DE number 1800367