Chromatic number stays stable when removing few graph edges

Impropriety and resilience of the chromatic number

Discrete Mathematics

Summary

This paper studies how the minimum number of colors needed to color a random graph, called the chromatic number, changes when some edges are removed. The authors found that as long as the removed edges are relatively few, the chromatic number remains almost the same, showing the coloring is resilient. They also link this stability to a related idea called improper coloring, where some coloring rules are relaxed. Their results match known cases where edges are added, providing a fuller picture of how robust graph coloring is against changes.

What this means in practice

  • For network engineers: Maintain network channel assignments that remain effective despite small disruptions removing some connections.
  • For distributed system architects: Design systems whose conflict-free resource allocations tolerate failures causing edge removals without increasing resource categories.

A theory result. No direct application yet.

Authors

Ross J. Kang, Colin McDiarmid

Abstract

We show that, for $p$ bounded away from $1$ and $np\to\infty$, the chromatic number of the binomial random graph $G_{n,p}$ is resilient to removal of a subgraph $H$ with $o(n \log(np))$ edges. It follows that the same assertion holds with $H$ being a subgraph of maximum degree $o(\log(np))$; and both these results are best possible up to a constant factor. We also prove corresponding results for the random $r$-regular graph $G_{n,r}$, when $r\to\infty$ and $r/n$ is bounded away from $1$, where $H$ has $o(n\log r)$ edges or maximum degree $o(\log r)$. 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 $G_{n,p}$ subject to the addition, rather than removal, of edges.