Proof of the mad conjecture and its coloring applications

Abstract

For a finite graph $G$, the maximum average degree $\mathrm{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 $\mathrm{mad}(G)<a+b$ admits a vertex partition $V(G)=A\cup B$ with $\mathrm{mad}(G[A])<a$ and $\mathrm{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 ${\chi }_{\star }(\mathrm{G})$ of a graph class $\mathrm{G}$ is the minimum integer $k$ such that, for some integer $c$, every graph in $\mathrm{G}$ has a $k$-coloring in which every monochromatic component has at most $c$ vertices. We apply this result to show that ${\chi }_{\star }({\mathrm{A}}_m)=\lfloor \frac{m}{2}\rfloor +1$, where ${\mathrm{A}}_m$ is the family of graphs $G$ with $\mathrm{mad}(G)\le m$. This solves an open problem posed in Wood's survey and highlighted by Hendrey and Wood. As another application of our general partition result for $\mathrm{mad}$, we obtain a bound for relaxed colorings. Namely, for non-negative integers $d_1,\dots ,d_k$, every graph $G$ with \[\operatorname{mad}(G)<\sum_{i=1}^k \frac{2d_i+2}{d_i+2}\] admits a partition $V(G)=V_1\cup \dots \cup V_k$ such that $\Delta (G[V_i])\le d_i$ for each $i\in [k]$. In particular, this provides the first non-trivial bounds for $k\ge 3$ with arbitrary $d_i$ and improves the previously known bound for $(d+1,d)$-colorings with $d\ge 2$.