On the strong chromatic number of graphs

Abstract

The strong chromatic number, $\ddot{I}{‡}_S(G)$, of an $n$-vertex graph $G$ is the smallest number $k$ such that after adding $k\lceil n/k\rceil -n$ isolated vertices to $G$ and considering {\bf any} partition of the vertices of the resulting graph into disjoint subsets $V_1,\dots ,V_{\lceil n/k\rceil }$ of size $k$ each, one can find a proper $k$-vertex-coloring of the graph such that each part $V_i$, $i=1,\dots ,\lceil n/k\rceil$, contains exactly one vertex of each color. For any graph $G$ with maximum degree $\hat{I}”$, it is easy to see that $\ddot{I}{‡}_S(G)\ge \hat{I}”+1$. Recently, Haxell proved that $\ddot{I}{‡}_S(G)\le 3\hat{I}”-1$. In this paper, we improve this bound for graphs with large maximum degree. We show that $\ddot{I}{‡}_S(G)\le 2\hat{I}”$ if $\hat{I}”\ge n/6$ and prove that this bound is sharp.

8 pages, 2 figures