Abstract
We derive eigenvalue bounds for the distance-t chromatic number of a graph, which is a generalization of the classical chromatic number. We apply such bounds to hypercube graphs, providing alternative spectral proofs for results by Ngo, Du and Graham [New bounds on a hypercube coloring problem, Inform. Process. Lett. 84(5) (2002) 265–269], and improving their bound for several instances. We also apply the eigenvalue bounds to Lee graphs, extending results by Kim and Kim [The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes, Discr. Appl. Math. 159(18) (2011) 2222–2228]. Finally, we provide a complete characterization for the existence of perfect Lee codes of minimum distance 3. In order to prove our results, we use a mix of spectral and number theory tools. Our results, which provide the first application of spectral methods to Lee codes, illustrate that spectral graph theory succeeds to capture the nature of the Lee metric.
| Original language | English |
|---|---|
| Article number | 2541024 |
| Journal | Journal of Algebra and its Applications |
| Volume | 24 |
| Issue number | 13n14 |
| DOIs | |
| Publication status | Published - Nov 2025 |
Bibliographical note
Publisher Copyright:© 2025 World Scientific Publishing Company.
Funding
Aida Abiad is supported by NWO (Dutch Research Council) through the grants VI.Vidi.213.085 and OCENW.KLEIN.475. Alessandro Neri is supported by the Research Foundation Flanders (FWO) through the grant 12ZZB23N. Luuk Reijnders is supported by NWO (Dutch Research Council) through the grant VI.Vidi.213.085. The authors thank Sjanne Zeijlemaker for the discussions on the LP implementation for Theorem 1.
| Funders | Funder number |
|---|---|
| Nederlandse Organisatie voor Wetenschappelijk Onderzoek | VI.Vidi.213.085, OCENW.KLEIN.475 |
| Fonds Wetenschappelijk Onderzoek | 12ZZB23N |
Keywords
- Distance chromatic number
- eigenvalues
- hypercube graph
- Lee graph
- perfect Lee code