Hostname: page-component-7c8c6479df-5xszh Total loading time: 0 Render date: 2024-03-27T04:46:20.522Z Has data issue: false hasContentIssue false

On the Strong Chromatic Number

Published online by Cambridge University Press:  03 November 2004

P. E. HAXELL
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 (e-mail: pehaxell@math.uwaterloo.ca)

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.

Type
Paper
Copyright
2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)