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
    0 references
    0 references
    0 references
    0 references

    Identifiers