Planar graphs without cycles of specific lengths (Q697075)

From MaRDI portal





scientific article; zbMATH DE number 1800367
Language Label Description Also known as
default for all languages
No label defined
    English
    Planar graphs without cycles of specific lengths
    scientific article; zbMATH DE number 1800367

      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