An improved bound for the strong chromatic number

Let η > 0 be given. Then there exists d₀ = d₀(η) such that the following holds. Let G be a finite graph with maximum degree at most d ≥ d₀ 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