An asymptotic bound for the strong chromatic number

Abstract: The strong chromatic number

c h i_{e x t s} (G)

of a graph

G

on

n

vertices is the least number

r

with the following property: after adding

r l c e i l n / r c e i l - n

isolated vertices to

G

and taking the union with any collection of spanning disjoint copies of

K_{r}

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

D e l t a (G) g e c n

,

c h i_{e x t s} (G) l e q (2 + o (1)) D e l t a (G)

, which is asymptotically best possible.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: An asymptotic bound for the strong chromatic number