Planar graphs without cycles of specific lengths (Q697075)

From MaRDI portal
Revision as of 10:27, 10 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
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