The Equitable Coloring of Circulant Graphs
Symmetry · 30.04.2026 · 18 (5) · 774
DOI: 10.3390/sym18050774 ↗Kurz gefasst
Fachartikel in der Zeitschrift Symmetry, online erschienen am 30.04.2026. Verfasst von Xiaoyu Jin und 2 weiteren Autor:innen. Die Arbeit nennt 19 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Key R&D Program of China, Shanxi Key Laboratory of Digital Design and Manufacturing.
Abstract (Originalsprache)
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|.
Förderung
- National Key R&D Program of China
- Shanxi Key Laboratory of Digital Design and Manufacturing
Zitieren
APA
Jin, X., Yan, G., & Yang, W. (2026). The Equitable Coloring of Circulant Graphs. Symmetry, 18(5), 774. https://doi.org/10.3390/sym18050774
Vancouver
Jin X, Yan G, Yang W. The Equitable Coloring of Circulant Graphs. Symmetry. 2026;18(5):774. doi:10.3390/sym18050774
BibTeX
@article{Jin2026,
author = {Jin, Xiaoyu and Yan, Guiying and Yang, Weihua},
title = {The Equitable Coloring of Circulant Graphs},
journal = {Symmetry},
year = {2026},
volume = {18},
number = {5},
pages = {774},
doi = {10.3390/sym18050774}
}
EUVIMED