pipette
ESEspañol

Impropriety and resilience of the chromatic number

Ross J. Kang, Colin McDiarmid

Preprint

In the authors' words

We show that, for bounded away from and , the chromatic number of the binomial random graph is resilient to removal of a subgraph with edges. It follows that the same assertion holds with being a subgraph of maximum degree ; and both these results are best possible up to a constant factor. We also prove corresponding results for the random -regular graph , when and is bounded away from , where has edges or maximum degree . Our results rely on a natural connection between chromatic resilience to edge removal and improper graph colouring. This work provides counterpoint to the work of Sudakov and Vu (2008) and Alon and Sudakov (2010), which treated chromatic resilience for subject to the addition, rather than removal, of edges.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 22 pages