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\equiv 8(\mathrm{mod}14)$ with $i\ge 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\le {\chi }_{\rho }(D(1,6))\le 20$, $18\le {\chi }_{\rho }(D(1,8))\le 22$, and ${\chi }_{\rho }(D(1,9))\le 17$.

45 pages, including the technical supplement. Computational data are available at https://doi.org/10.5281/zenodo.22562359