pipette
ENEnglish

Impropriety and resilience of the chromatic number

Ross J. Kang, Colin McDiarmid

Preprint

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 22 pages