# An asymptotic bound for the strong chromatic number

Research output: Contribution to journal › Article

## Standard

**An asymptotic bound for the strong chromatic number.** / Lo, Allan; Sanhueza Matamala, Nicolas.

Research output: Contribution to journal › Article

## Harvard

*Combinatorics, Probability and Computing*, vol. 28, no. 5, pp. 768-776. https://doi.org/10.1017/S0963548318000561

## APA

*Combinatorics, Probability and Computing*,

*28*(5), 768-776. https://doi.org/10.1017/S0963548318000561

## Vancouver

## Author

## Bibtex

}

## RIS

TY - JOUR

T1 - An asymptotic bound for the strong chromatic number

AU - Lo, Allan

AU - Sanhueza Matamala, Nicolas

PY - 2019/9

Y1 - 2019/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85063064136&partnerID=8YFLogxK

U2 - 10.1017/S0963548318000561

DO - 10.1017/S0963548318000561

M3 - Article

VL - 28

SP - 768

EP - 776

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

IS - 5

ER -