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.
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.