EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Eigenvalue bounds for distance-edge colourings

Aida Abiad, Harper Reijnders

Discrete Applied Mathematics · 2026-10 · 391 · 176-191

DOI: 10.1016/j.dam.2026.04.043 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2026-10. Verfasst von Aida Abiad und 1 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Dutch Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For a fixed positive integer $t$, we consider the graph colouring problem in which edges at distance at most $t$ are given distinct colours. We obtain sharp lower bounds for the distance-$t$ chromatic index, the least number of colours necessary for such a colouring. Our bounds are of algebraic nature; they depend on the eigenvalues of the line graph and on a polynomial which can be found using integer linear programming methods. We show several graph classes that attain equality for our bounds, and also present some computational results which illustrate the bound's performance. Lastly, we investigate the implications the spectral approach has to the Erd\H{o}s-Ne\v{s}et\v{r}il conjecture, and derive some conditions which a graph must satisfy if we could use it to obtain a counter example through the proposed spectral methods.

Förderung

  • Dutch Research Council

Zitieren

APA

Abiad, A., & Reijnders, H. (2026). Eigenvalue bounds for distance-edge colourings. Discrete Applied Mathematics, 391, 176-191. https://doi.org/10.1016/j.dam.2026.04.043

Vancouver

Abiad A, Reijnders H. Eigenvalue bounds for distance-edge colourings. Discrete Applied Mathematics. 2026;391:176-191. doi:10.1016/j.dam.2026.04.043

BibTeX
@article{Abiad2026,
  author = {Abiad, Aida and Reijnders, Harper},
  title = {Eigenvalue bounds for distance-edge colourings},
  journal = {Discrete Applied Mathematics},
  year = {2026},
  volume = {391},
  pages = {176--191},
  doi = {10.1016/j.dam.2026.04.043}
}
Kostenlos starten →