Proof of the mad conjecture and its coloring applications
Abstract
For a finite graph G, the maximum average degree 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 mad(G)<a+b admits a vertex partition V(G)=A∪ B with mad(G[A])<a and 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 χ⋆(G) of a graph class G is the minimum integer k such that, for some integer c, every graph in G has a k-coloring in which every monochromatic component has at most c vertices. We apply this result to show that χ⋆(Am)=⌊m/2⌋+1, where Am is the family of graphs G with mad(G)≤ 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 mad, we obtain a bound for relaxed colorings. Namely, for non-negative integers d1,…,dk, every graph G with mad(G)<∑i=1k (2di+2)/(di+2) admits a partition V(G)=V1∪…∪ Vk such that Δ(G[Vi])≤ di for each i∈[k]. In particular, this provides the first non-trivial bounds for k≥3 with arbitrary di and improves the previously known bound for (d+1,d)-colorings with d ≥ 2.
Related
- A proof of Wang's planar D-coloring conjecture
- Sparse coloring for isosceles-free grids: an AI-assisted proof case study
- The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs
- The List Edge-Coloring Conjecture for New Infinite Families
- Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples
BibTeX
@misc{grzesik2026proof,
title = {{Proof of the mad conjecture and its coloring applications}},
author = {Andrzej Grzesik and Lenka Kopfová and Gaurav Kucheriya and Binlong Li and Magdalena Prorok},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04645},
eprint = {2610.04645},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04645},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Proof of the mad conjecture and its coloring applications
AU - Andrzej Grzesik
AU - Lenka Kopfová
AU - Gaurav Kucheriya
AU - Binlong Li
AU - Magdalena Prorok
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04645
UR - https://arxiv.org/abs/2610.04645
AB - For a finite graph G, the maximum average degree 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 mad(G)<a+b admits a vertex partition V(G)=A∪ B with mad(G[A])<a and 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 χ_⋆(G) of a graph class G is the minimum integer k such that, for some integer c, every graph in G has a k-coloring in which every monochromatic component has at most c vertices. We apply this result to show that χ_⋆(A_m)=⌊m/2⌋+1, where A_m is the family of graphs G with mad(G)≤ 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 mad, we obtain a bound for relaxed colorings. Namely, for non-negative integers d_1,…,d_k, every graph G with mad(G)<∑_i=1^k (2d_i+2)/(d_i+2) admits a partition V(G)=V_1∪…∪ V_k such that Δ(G[V_i])≤ d_i for each i∈[k]. In particular, this provides the first non-trivial bounds for k≥3 with arbitrary d_i and improves the previously known bound for (d+1,d)-colorings with d ≥ 2.
ER -