1. Revisiting Semistrong Edge-Coloring of Graphs
- Author
-
Lužar, Borut, Mockovčiaková, Martina, and Soták, Roman
- Subjects
FOS: Computer and information sciences ,05C15 ,Discrete Mathematics (cs.DM) ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics - Abstract
A matching $M$ in a graph $G$ is {\em semistrong} if every edge of $M$ has an endvertex of degree one in the subgraph induced by the vertices of $M$. A {\em 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\'{a}rf\'{a}s and Hubenko ({Semistrong edge coloring of graphs}. \newblock {\em 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.
- Published
- 2022
- Full Text
- View/download PDF