A Brooks-type bound for squares of K-4-minor-free graphs

Kostochka A. V. , Ozkahya L. , Woodall D. R.

DISCRETE MATHEMATICS, cilt.309, ss.6572-6584, 2009 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 309
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1016/j.disc.2009.07.004
  • Dergi Adı: DISCRETE MATHEMATICS
  • Sayfa Sayıları: ss.6572-6584

Özet

Refining a bound by Lih, Wang and Zhu, we prove that if the square G(2) of a K-4-minor-free graph G with maximum degree Delta >= 6 does not contain a complete subgraph on [3/2 Delta] + 1 vertices, then G(2) is [3/2 Delta]-colorable. (C) 2009 Elsevier B.V. All rights reserved.