On the Strong Chromatic Number
Let $G$ be a finite graph with maximum degree at most $d$. Then, for every partition of $V(G)$ into classes of size $3d-1$, there exists a proper colouring of $G$ with $3d-1$ colours in which each class receives all $3d-1$ colours.(Published Online November 3 2004)
(Received May 20 2002)
(Revised July 2 2003)
1 Research supported in part by NSERC. This work was done while the author was on leave at Bell Labs Lucent Technologies.