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

Kostochka, Alexandr; Ozkahya, LALE; Woodall, Douglas

doi:10.1016/j.disc.2009.07.004

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, Scopus)

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.