Strong edge coloring of subcubic bipartite graphs

arXiv1311.6668MaRDI QIDQ6246779FDOQ6246779

Riste Škrekovski, Borut Lužar, Roman Soták, Martina Mockovčiaková

Publication date: 26 November 2013

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.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Strong edge coloring of subcubic bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6246779)