Combinatorics, Probability and Computing



Paper

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: pehaxell@math.uwaterloo.ca)

Article author query
haxell pe   [Google Scholar] 
 

Abstract

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)



Footnotes

1 Research supported in part by NSERC. This work was done while the author was on leave at Bell Labs Lucent Technologies.