The Equitable Coloring of Circulant Graphs

A proper vertex coloring is equitable if the sizes of any two color classes differ by at most one. Any graph G with maximum degree Δ(G) admits an equitable Δ(G)+1-coloring, computable in O(Δ(G)n2) time for n vertices. A circulant graph G(n;D) is the graph with vertex set Zn and two vertices x,y are adjacent if |x−y|∈±Dmodn. The partitioning problem in parallel decoding of multi-edge QC-LDPC codes can be interpreted as an equitable coloring problem. We prove some upper bounds for χ=(G(n;D)) and develop equitable coloring algorithms, including pattern-based periodic coloring and step-based coloring. The proposed methods typically use fewer than Δ(G)+1 colors and have computational complexity lower than O(Δ(G)n2) for circulant graphs G(n;D) with small |D|.