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.