Haxell, Penny E.

Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

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

\begin{conjecture} If $\Delta$ is the maximal degree of a graph $G$, then $G$ is strongly $2 \Delta$-colorable. \end{conjecture}

Keywords: strong coloring