Theoretical aspects of equitable partition of networks into sparse modules

Abstract The problem of partitioning a large complex network equitably into sparse modules with given rules can be modeled by the equitable list d-degenerate coloring of graphs. This paper establishes theoretical results on such a coloring based on a newly proposed conjecture which states that every graph G is equitably d-degenerate k-colorable and equitably d-degenerate k-choosable for every integer k ≥ ( Δ ( G ) + 1 ) / ( d + 1 ) . This conjecture is strong as it implies the Hajnal-Szemeredi theorem on equitable coloring, the equitable list coloring conjecture (Kostochka, Pelsmajer, and West, 2003), the equitable vertex arboricity conjecture (Wu, Zhang, and Li, 2013), and the equitable list vertex arboricity conjecture (Zhang, 2016). In this paper, we confirm this unified conjecture for globally coupled networks, ( d + 1 ) -degenerate graphs, graphs with bounded maximum average degree, and planar graphs with large maximum degree. The equitable d-degenerate k-colorability part of this conjecture is also verified for interval graphs, generalizing a result of Niu, Li, and Zhang (2021).