On Gallai d-colored circulants
Abstract
A d-graph is a complete graph whose edges are colored with colors from [d]. It is Gallai if it contains no triangle whose three edges have distinct colors. We prove that every Gallai d-circulant is an iterated lexicographic product of circulants using at most two colors. The proof uses the compatibility of the known canonical modular decomposition with the cyclic action. For d-graphs avoiding both a rainbow triangle Δ and the two-colored four-vertex graph Π whose chromatic components are paths, we give a more explicit classification. Color-preserving vertex transitivity is equivalent to circular symmetry and to a reduced positional game tree whose branching numbers and labels depend only on depth. The edge colors in the given cyclic labeling are determined by a chain of divisors of the order. This description yields a complete isomorphism invariant and a linear-time recognition procedure in the difference-word representation. The characterization of CIS d-circulants reduces to CIS two-colored factors. Finally, we extend the numerical CIS criterion to d-graphs whose chromatic components are vertex-transitive.
Related
- Complete Determination of the Gallai--van der Waerden Number GW(r;3,3)
- A proof of the Erdős-Gallai cycle decomposition conjecture
- Signed circulants at the Ramanujan bound
- The 3-Color 2-Chromatic Gallai-Ramsey Number for Complete Graphs
- Two-basepoint Terwilliger algebras and the quantum symmetry of prime-order circulants
BibTeX
@misc{gurvich2026gallai,
title = {{On Gallai $d$-colored circulants}},
author = {Vladimir Gurvich and Mariya Naumova},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03695},
eprint = {2611.03695},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03695},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On Gallai d-colored circulants
AU - Vladimir Gurvich
AU - Mariya Naumova
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.03695
UR - https://arxiv.org/abs/2611.03695
AB - A d-graph is a complete graph whose edges are colored with colors from [d]. It is Gallai if it contains no triangle whose three edges have distinct colors. We prove that every Gallai d-circulant is an iterated lexicographic product of circulants using at most two colors. The proof uses the compatibility of the known canonical modular decomposition with the cyclic action. For d-graphs avoiding both a rainbow triangle Δ and the two-colored four-vertex graph Π whose chromatic components are paths, we give a more explicit classification. Color-preserving vertex transitivity is equivalent to circular symmetry and to a reduced positional game tree whose branching numbers and labels depend only on depth. The edge colors in the given cyclic labeling are determined by a chain of divisors of the order. This description yields a complete isomorphism invariant and a linear-time recognition procedure in the difference-word representation. The characterization of CIS d-circulants reduces to CIS two-colored factors. Finally, we extend the numerical CIS criterion to d-graphs whose chromatic components are vertex-transitive.
ER -