2025/09/21 by Lin, Yuquan, Lin, Wensong
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.17069
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 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 semistrong chromatic index χ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≤2 and is NP-complete for k≥3. For trees, we develop a polynomial-time algorithm to determine the semistrong chromatic index exactly.