TOPICS
Search

Clustered Coloring


A clustered coloring assigns colors to the vertices of a graph so that each monochromatic connected component has at most a prescribed number of vertices. Unlike a proper coloring, it permits adjacent vertices to have the same color. The clustered chromatic number of a class of graphs is the least number of colors that suffices with a uniform bound on the sizes of monochromatic connected components.

Grzesik et al. (2026) proved that the class of finite simple graphs of maximum average degree at most m>0 has clustered chromatic number |_m/2_|+1, where |_x_| is the floor function. More specifically, for nonnegative integers d_1,...,d_k, every graph G satisfying

 mad(G)<sum_(i=1)^k(2d_i+2)/(d_i+2)

has an assignment of colors 1, ..., k to its vertices in which the monochromatic connected components of color i have at most d_i+1 vertices. This also bounds their maximum vertex degree by d_i and gives a defective coloring.


See also

Clustered Chromatic Number, Defective Coloring, Maximum Average Degree, Proper Coloring, Vertex Coloring

Explore with Wolfram|Alpha

References

Grzesik, A.; Kopfová, L.; Kucheriya, G.; Li, B.; and Prorok, M. "Proof of the mad Conjecture and Its Coloring Applications." 3 Oct 2026. https://arxiv.org/abs/2610.04645.

Cite this as:

Weisstein, Eric W. "Clustered Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ClusteredColoring.html

Subject classifications