An improved bound for the strong chromatic number

Let eta > 0 be given. Then there exists d(0) = d(0)(eta) such that the following holds. Let G be a finite graph with maximum degree at most d >= d(0) whose vertex set is partitioned into classes of size alpha d, where alpha >= 11/4 + eta. Then there exists a proper coloring of G with alpha d colors in which each class receives all alpha d colors. (C) 2008 Wiley Periodicals, Inc.