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


Files produced by the author(s)


  • HAL Id : hal-02548191, version 1



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



Record views


Files downloads