Importance: High ✭✭✭
 Author(s): Aharoni, Ron Alon, Noga Haxell, Penny E.
 Subject: Graph Theory » Coloring » » Vertex coloring
 Keywords: strong coloring
 Recomm. for undergrads: no
 Posted by: berger on: March 27th, 2007

Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.

Conjecture   If is the maximal degree of a graph , then is strongly -colorable.

Haxell proved that if is the maximal degree of a graph , then is strongly -colorable. She later proved that the strong chromatic number is at most for sufficiently large depending on . Aharoni, Berger, and Ziv proved the fractional relaxation.