On the strong chromatic number of graphs

Original · EN

The strong chromatic number, χₛ(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 V₁,, V n/k of size k each, one can find a proper k-vertex-coloring of the graph such that each part Vᵢ, i=1,, n/k, contains exactly one vertex of each color. For any graph G with maximum degree Δ, it is easy to see that χₛ(G)≥Δ+1. Recently, Haxell proved that χₛ(G) ≤ 3Δ-1. In this paper, we improve this bound for graphs with large maximum degree. We show that χₛ(G)≤ 2Δ if Δ≥ n/6 and prove that this bound is sharp.