Article contents
An asymptotic bound for the strong chromatic number
Published online by Cambridge University Press: 15 March 2019
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\lceil n/r\rceil-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.
MSC classification
- Type
- Paper
- Information
- Copyright
- © Cambridge University Press 2019
Footnotes
The research leading to these results was partially supported by EPSRC, grant no. EP/P002420/1.
The research leading to these results was partially supported by the Becas Chile scholarship scheme from CONICYT.
References
- 4
- Cited by