Revisiting Semistrong Edge-Coloring of Graphs
share
A matching M in a graph G is semistrong if every edge of M has an endvertex of degree one in the subgraph induced by the vertices of M. A semistrong edge-coloring of a graph G is a proper edge-coloring in which every color class induces a semistrong matching. In this paper, we continue investigation of properties of semistrong edge-colorings initiated by Gyárfás and Hubenko (Semistrong edge coloring of graphs. J. Graph Theory, 49 (2005), 39–47). We establish tight upper bounds for general graphs and for graphs with maximum degree 3. We also present bounds about semistrong edge-coloring which follow from results regarding other, at first sight non-related, problems. We conclude the paper with several open problems.
READ FULL TEXT