An asymptotic bound for the strong chromatic number

Research output: Contribution to journalArticle

Standard

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

In: Combinatorics, Probability and Computing, Vol. 28, No. 5, 09.2019, p. 768-776.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Lo, Allan ; Sanhueza Matamala, Nicolas. / An asymptotic bound for the strong chromatic number. In: Combinatorics, Probability and Computing. 2019 ; Vol. 28, No. 5. pp. 768-776.

Bibtex

@article{9b4ab228a75447f8a6d4329a19e3f918,
title = "An asymptotic bound for the strong chromatic number",
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.",
author = "Allan Lo and {Sanhueza Matamala}, Nicolas",
year = "2019",
month = sep
doi = "10.1017/S0963548318000561",
language = "English",
volume = "28",
pages = "768--776",
journal = "Combinatorics, Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",
number = "5",

}

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 -