Semistrong edge colorings of planar graphs

Abstract

Strengthened notions of a matching $M$ of a graph $G$ have been considered, requiring that the matching $M$ has some properties with respect to the subgraph $G_M$ of $G$ induced by the vertices covered by $M$: If $M$ is the unique perfect matching of $G_M$, then $M$ is a \emph{uniquely restricted matching} of $G$; if all the edges of $M$ are pendant edges of $G_M$, then $M$ is a \emph{semistrong matching} of $G$; if all the vertices of $G_M$ are pendant, then $M$ is an \emph{induced matching} of $G$. Strengthened notions of edge coloring and of the chromatic index follow. In this paper, we consider the maximum semistrong chromatic index of planar graphs with given maximum degree $\Delta$. We prove that graphs with maximum average degree less than $14/5$ have semistrong chromatic index (hence uniquely restricted chromatic index) at most $2\Delta +4$, and we reduce the bound to $2\Delta +2$ if the maximum average degree is less than $8/3$. These cases cover, in particular, the cases of planar graphs with girth at least 7 (resp. at least 8). Our result makes some progress on the conjecture of Lu{ž}ar, Mockov{č}iakov{á} and Sot{á}k [J.~Graph Theory 105 (2024) 612--632], which asserts that every planar graph $G$ has a semistrong edge coloring with $2\Delta +C$ colors, for some universal constant $C$. (Note that such a conjecture would fail for strong edge coloring as there exist graphs with arbitrarily large maximum degree that are not strongly $(4\Delta -5)$-edge-colorable.) We provide an example of a planar graph showing that the maximum semistrong chromatic index of planar graphs with maximum degree $\Delta$ is at least $2\Delta +4$.

References in corpus (1)

• Revisiting Semistrong Edge-Coloring of Graphs