An asymptotic bound for the strong chromatic number

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

Abstract

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.

Details

Original languageEnglish
Pages (from-to)768-776
Number of pages9
JournalCombinatorics, Probability and Computing
Volume28
Issue number5
Early online date15 Mar 2019
Publication statusPublished - Sep 2019