Impropriety and resilience of the chromatic number
Source: arxiv.org/abs/2611.11280
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.11280
curl -X POST /api/v1/records/arxiv/2611.11280/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.11280/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'