Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

An algorithmic framework for colouring locally sparse graphs

Abstract : We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed k ≥ 3 and ε > 0, a randomised polynomial-time algorithm for colouring graphs of maximum degree ∆ in which each vertex is contained in at most t copies of a cycle of length k, where 1/2 ≤ t ≤ ∆^(2ε / (1+2ε)) / (log ∆) 2 , with (1 + ε)∆/ log(∆/ √ t) colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor 2 and it coincides with a famous algorithmic barrier to colouring random graphs.
Complete list of metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02548191
Contributor : Jean-Sébastien Sereni <>
Submitted on : Monday, April 20, 2020 - 3:21:36 PM
Last modification on : Wednesday, August 5, 2020 - 3:01:27 AM

File

hcm_cs.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02548191, version 1

Collections

Citation

Ewan Davies, Ross Kang, François Pirot, Jean-Sébastien Sereni. An algorithmic framework for colouring locally sparse graphs. 2020. ⟨hal-02548191⟩

Share

Metrics

Record views

19

Files downloads

14