An asymptotic bound for the strong chromatic number

Abstract

The strong chromatic number ${\chi }_{\text{s}}(G)$ of a graph $G$ on $n$ vertices is the least number $r$ with the following property: after adding $r\lceil n/r\rceil -n$ isolated vertices to $G$ and taking the union with any collection of spanning disjoint copies of $K_r$ in the same vertex set, the resulting graph has a proper vertex-colouring with $r$ colours. We show that for every $c>0$ and every graph $G$ on $n$ vertices with $\Delta (G)\ge cn$, ${\chi }_{\text{s}}(G)\le (2+o(1))\Delta (G)$, which is asymptotically best possible.

Minor correction, accepted for publication in Combin. Probab. Comput

References in corpus (1)

• On the strong chromatic number of graphs

Cited by in corpus (1)

• Powers of Hamiltonian cycles in multipartite graphs