An improved bound for the strong chromatic number
Penny E. Haxell · Journal of Graph Theory · 2008
Abstract Let η > 0 be given. Then there exists d0 = d0(η) such that the following holds. Let G be a finite graph with maximum degree at most d ≥ d0 whose vertex set is partitioned into classes of size α d, where α≥ 11/4 + η. Then there exists a proper coloring of G with αd colors in which each class receives all αd colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:148–158, 2008