A sufficient condition for the square of a line graph to be perfect
Ars Combinatoria · 19.07.2026 · 168 · 3-16
DOI: 10.61091/ars168-01 ↗Kurz gefasst
Fachartikel in der Zeitschrift Ars Combinatoria, online erschienen am 19.07.2026. Verfasst von A. Y. M. Chin und 3 weiteren Autor:innen.
Abstract (Originalsprache)
In this paper, we prove that if a graph does not contain any cycle of length greater than \(4\), then the square of its line graph is perfect. As an application, we give a concise proof of a known result: the strong chromatic index of a bipartite graph that does not contain any cycle of length greater than \(4\) is at most \(\Delta^2\), where \(\Delta\) represents the maximum degree of the graph. This latter result provides a partial affirmative answer to some known conjectures on upper bounds for the strong chromatic index of graphs.
Zitieren
APA
Chin, A. Y. M., Maimani, H. R., Pournaki, M. R., & Yassemi, S. (2026). A sufficient condition for the square of a line graph to be perfect. Ars Combinatoria, 168, 3-16. https://doi.org/10.61091/ars168-01
Vancouver
Chin AYM, Maimani HR, Pournaki MR, Yassemi S. A sufficient condition for the square of a line graph to be perfect. Ars Combinatoria. 2026;168:3-16. doi:10.61091/ars168-01
BibTeX
@article{Chin2026,
author = {Chin, A. Y. M. and Maimani, H. R. and Pournaki, M. R. and Yassemi, S.},
title = {A sufficient condition for the square of a line graph to be perfect},
journal = {Ars Combinatoria},
year = {2026},
volume = {168},
pages = {3--16},
doi = {10.61091/ars168-01}
}
EUVIMED