EUVIMEDEUVIMED entdecken
Crossref

Computational results on semistrong edge coloring of graphs

Yuquan Lin, Wensong Lin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →