Density regions, integer certificates and packing colorings of distance graphs
Abstract
We study simultaneous color densities in packing colorings of integer distance graphs. For D(1,6), we determine several exact density regions and prove that colors $1$ through $7$ have maximum combined density 211/252. When this maximum is approached, the seven individual color frequencies are forced to converge to a specified vector. On an optimal low-color layer, some density vectors have nonperiodic realizations but no periodic realization; we determine how much accumulated density loss is necessary for switching between the relevant configurations. For sufficiently large additional color indices, a fixed finite graph describes the joint density region. In particular, we determine a seven-vertex region for every i≡8pmod14 with i≥36 and prove that $36$ is the first stable index in this residue class. The proofs combine finite-state integer certificates with explicit constructions and limit arguments. Applications give 17≤χρ(D(1,6))≤20, 18≤χρ(D(1,8))≤22, and χρ(D(1,9))≤17.
Related
- Optimizing Explicit Unit-Distance Lower-Bound Certificates
- Multiset Colorings of Random Graphs Across Density Regimes
- Fast rigid rotational alignment of voxelized 3-D density maps in sliced Wasserstein distance
- A Hajnal-Szemerédi Theorem for Skewed Colorings
- Sampling Line-Graph Colorings with Constant Extra Colors
BibTeX
@misc{zhang2026density,
title = {{Density regions, integer certificates and packing colorings of distance graphs}},
author = {Enkai Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09018},
eprint = {2609.09018},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09018},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Density regions, integer certificates and packing colorings of distance graphs
AU - Enkai Zhang
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09018
UR - https://arxiv.org/abs/2609.09018
AB - We study simultaneous color densities in packing colorings of integer distance graphs. For D(1,6), we determine several exact density regions and prove that colors $1$ through $7$ have maximum combined density 211/252. When this maximum is approached, the seven individual color frequencies are forced to converge to a specified vector. On an optimal low-color layer, some density vectors have nonperiodic realizations but no periodic realization; we determine how much accumulated density loss is necessary for switching between the relevant configurations. For sufficiently large additional color indices, a fixed finite graph describes the joint density region. In particular, we determine a seven-vertex region for every i≡8pmod14 with i≥36 and prove that $36$ is the first stable index in this residue class. The proofs combine finite-state integer certificates with explicit constructions and limit arguments. Applications give 17≤χ_ρ(D(1,6))≤20, 18≤χ_ρ(D(1,8))≤22, and χ_ρ(D(1,9))≤17.
ER -