Obstructions to coloring arithmetic graphs
Abstract
The arithmetic graph Bn joins distinct a,b∈N when max(a,b)/gcd(a,b)≤ n. We prove χ(B205)=206, disproving the conjecture that χ(Bn)=n for every n, equivalently the Rainbow Cascades Conjecture. The proof reduces an arbitrary tiling by the arithmetic exponent tile to a periodic tiling, then to two families of finite quotients, which are excluded using exact computations. We also construct a $208$-coloring using Z104×Z2 and prove 212≤χ(B211)≤213. The lower bound at $211$ follows from prime-cardinality tiling rigidity and the published nonexistence of a cyclic logarithm of length $211$; we give a direct proof of the required rigidity statement. Finally, we record the equivalence with the List Cascade Coloring Conjecture and the conjecture on ironic decorations, and deduce finite graph counterexamples to both. The least n with χ(Bn)>n is either $195$ or $205$; determining which remains open.
Related
- Bounds for B-coloring planar and outerplanar graphs
- COLORING SEMIMINIMAL CAYLEY GRAPHS
- Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
- Coloring sparse random Cayley graphs
- Strong edge coloring of graphs with maximum degree $6$
BibTeX
@misc{wang2026obstructions,
title = {{Obstructions to coloring arithmetic graphs}},
author = {Lujia Wang and Ruihua Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15081},
eprint = {2609.15081},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15081},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Obstructions to coloring arithmetic graphs
AU - Lujia Wang
AU - Ruihua Wang
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15081
UR - https://arxiv.org/abs/2609.15081
AB - The arithmetic graph B_n joins distinct a,b∈N when max(a,b)/gcd(a,b)≤ n. We prove χ(B_205)=206, disproving the conjecture that χ(B_n)=n for every n, equivalently the Rainbow Cascades Conjecture. The proof reduces an arbitrary tiling by the arithmetic exponent tile to a periodic tiling, then to two families of finite quotients, which are excluded using exact computations. We also construct a $208$-coloring using Z_104×Z_2 and prove 212≤χ(B_211)≤213. The lower bound at $211$ follows from prime-cardinality tiling rigidity and the published nonexistence of a cyclic logarithm of length $211$; we give a direct proof of the required rigidity statement. Finally, we record the equivalence with the List Cascade Coloring Conjecture and the conjecture on ironic decorations, and deduce finite graph counterexamples to both. The least n with χ(B_n)>n is either $195$ or $205$; determining which remains open.
ER -