{"id":"arxiv/2611.11280","url":"https://arxiv.org/abs/2611.11280","tags":["math.CO","cs.DM","math.PR"],"score":0,"title":"Impropriety and resilience of the chromatic number","domain":"math.CO","source":"arxiv","authors":["Ross J. Kang","Colin McDiarmid"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-08","reactions":{}}