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-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 309
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1016/j.disc.2009.07.004
  • Dergi Adı: DISCRETE MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.6572-6584
  • Hacettepe Üniversitesi Adresli: Hayır

Ö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.