An asymptotic bound for the strong chromatic number. (15th September 2019)

• Record Type: Journal Article
• Authors: Lo, Allan; Sanhueza-Matamala, Nicolás
• Is Part Of: Combinatorics, probability and computing. Volume 28:Number 5(2019)
• Page Start: 768
• Page End: 776
• Publication Date: 2019-09-15
• Subjects: Primary 05C15, -- Secondary 05C70, -- 05C35; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548318000561
• Languages: English
• ISSNs: 0963-5483

Abstract

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.