Yuquan Lin, Wensong Lin
ABSTRACT In this work, we study two relaxations of the well‐known strong edge coloring. A semistrong edge coloring of a graph is an edge coloring in which every color class forms a matching such that every edge of is incident with (at least) one vertex of degree 1 in the subgraph of induced by the vertices covered by . For any two nonnegative integers and , an ‐ relaxed strong edge coloring of is an edge coloring in which, for every edge of , at most edges at distance 1 and at most edges at distance 2 from receive the same color as . The corresponding chromatic indices are defined accordingly. We confirm a recent conjecture of Lužar, Mockovčiaková, and Soták [J. Graph Theory 105 (2024) 612‐632], which asserts that every connected graph with maximum degree (), except for , has a semistrong chromatic index at most . This is achieved by constructing an edge coloring of using at most colors that is simultaneously semistrong and ‐relaxed strong. Consequently, every such graph also has ‐relaxed strong chromatic index at most .