An asymptotic bound for the strong chromatic number
Research output: Contribution to journal › Article › peer-review
Colleges, School and Institutes
The strong chromatic number χs(G) of a graph G on n vertices is the least number r with the following property: after adding r⌈n/r⌉−n isolated vertices to G and taking the union with any collection of spanning disjoint copies of Kr 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 Δ(G)≥cn, χs(G)≤(2+o(1))Δ(G), which is asymptotically best possible.
|Number of pages||9|
|Journal||Combinatorics, Probability and Computing|
|Early online date||15 Mar 2019|
|Publication status||Published - Sep 2019|