On the strong chromatic number of graphs

Abstract

The strong chromatic number, \(\chi_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, \ldots, 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, \ldots, \lceil n/k\rceil\), contains exactly one vertex of each color. For any graph \(G\) with maximum degree \(\Delta\), it is easy to see that \(\chi_S(G)\geq\Delta+1\). Recently, Haxell proved that \(\chi_S(G) \leq 3\Delta -1\). In this paper, we improve this bound for graphs with large maximum degree. We show that \(\chi_S(G)\leq 2\Delta\) if \(\Delta \geq n/6\) and prove that this bound is sharp.