On the strong chromatic number of graphs
Maria Axenovich, Ryan R. Martin · 2006
The strong chromatic number, χS(G), of an n-vertex graph G is the smallest number k such that after adding k⌈n/k ⌉ − n isolated vertices to G and considering any partition of the vertices of the resulting graph into disjoint subsets V1,..., V ⌈n/k ⌉ of size k each, one can find a proper k-vertex-coloring of the graph such that each part Vi, i = 1,..., ⌈n/k⌉, contains exactly one vertex of each color. For any graph G with maximum degree ∆, it is easy to see that χS(G) ≥ ∆ + 1. Recently, Haxell proved that χS(G) ≤ 3 ∆ − 1. In this paper, we improve this bound for graphs with large maximum degree. We show that χS(G) ≤ 2 ∆ if ∆ ≥ n/6 and prove that this bound is sharp. 1