Impropriety and resilience of the chromatic number
En palabras de los autores
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.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 22 pages