Combinatorics, Probability and Computing


On the Strong Chromatic Number

P. E. HAXELL a1 1
a1 Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 (e-mail:

Article author query
haxell pe   [Google Scholar] 


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.