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 
has clustered
chromatic number 
,
where 
is the floor function. More specifically, for nonnegative integers 
, every graph 
satisfying
 |
has an assignment of colors 1, ..., 
to its vertices in which the
monochromatic connected components of color
have at most 
vertices. This also bounds their maximum
vertex degree by 
and gives a defective coloring.
Grzesik et al. (2026) state that ChatGPT-5.6 Sol suggested the potential function for the underlying partition theorem, but that they developed the final proof after finding its proposed technical lemma difficult to verify.
