Strong edge coloring of subcubic bipartite graphs

Abstract

A strong edge coloring of a graph $G$ is a proper edge coloring in which each color class is an induced matching of $G$. In 1993, Brualdi and Quinn Massey proposed a conjecture that every bipartite graph without $4$-cycles and with the maximum degrees of the two partite sets $2$ and $\Delta$ admits a strong edge coloring with at most $\Delta +2$ colors. We prove that this conjecture holds for such graphs with $\Delta =3$. We also confirm the conjecture proposed by Faudree et al. for subcubic bipartite graphs.

References in corpus (1)

• A Strong Edge-Coloring of Graphs with Maximum Degree 4 Using 22 Colors