Proof of the mad conjecture and its coloring applications

Andrzej Grzesik, Lenka Kopfová, Gaurav Kucheriya, Binlong Li, Magdalena Prorok

arXivarxiv/2610.04645Oct 3, 2026math.COscore 0

For a finite graph $G$, the maximum average degree $\operatorname{mad}(G)$ is the largest average degree of a nonempty subgraph of $G$. Hendrey, Norin and Wood asked whether this parameter is partitionable, that is, whether for all positive reals $a,b$ every graph $G$ with $\operatorname{mad}(G)<a+b$ admits a vertex partition $V(G)=A\cup B$ with $\operatorname{mad}(G[A])<a$ and $\operatorname{mad}(G[B])<b$. In this note, we answer this question affirmatively. Moreover, we generalize this to an arbitrary number of partition classes. The clustered chromatic number $χ_\star(\mathrm{G})$ of a…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.04645
curl -X POST /api/v1/records/arxiv/2610.04645/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.04645/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'