Computational results on semistrong edge coloring of graphs
Discrete Applied Mathematics · 2026-10 · 391 · 399-412
DOI: 10.1016/j.dam.2026.05.003 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2026-10. Verfasst von Yuquan Lin und 1 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben. Gefördert von: China Scholarship Council, National Natural Science Foundation of China.
Abstract (Originalsprache)
The semistrong edge coloring, as a relaxation of the well-known strong edge coloring, can be used to model efficient communication scheduling in wireless networks. An edge coloring of a graph $G$ is called \emph{semistrong} if every color class $M$ is a matching such that every edge of $M$ is incident with a vertex of degree 1 in the subgraph of $G$ induced by the endvertices of edges in $M$. The \emph{semistrong chromatic index} $\chi_{ss}'(G)$ of $G$ is the minimum number of colors required for a semistrong edge coloring. In this paper, we prove that the problem of determining whether a graph $G$ has a semistrong edge coloring with $k$ colors is polynomial-time solvable for $k\le2$ and is NP-complete for $k\ge3$. For trees, we develop a polynomial-time algorithm to determine the semistrong chromatic index exactly.
Förderung
- China Scholarship Council
- National Natural Science Foundation of China
Zitieren
APA
Lin, Y., & Lin, W. (2026). Computational results on semistrong edge coloring of graphs. Discrete Applied Mathematics, 391, 399-412. https://doi.org/10.1016/j.dam.2026.05.003
Vancouver
Lin Y, Lin W. Computational results on semistrong edge coloring of graphs. Discrete Applied Mathematics. 2026;391:399-412. doi:10.1016/j.dam.2026.05.003
BibTeX
@article{Lin2026,
author = {Lin, Yuquan and Lin, Wensong},
title = {Computational results on semistrong edge coloring of graphs},
journal = {Discrete Applied Mathematics},
year = {2026},
volume = {391},
pages = {399--412},
doi = {10.1016/j.dam.2026.05.003}
}
EUVIMED