A note on the strong chromatic index of bipartite graphs (Q932702): Difference between revisions

A strong edge-coloring of a graph \(G\) is an edge-coloring in which every color class is an induced matching; that is, if edges \(uv\) and \(wz\) have the same color, then the pair \(uw, uz, vw\) and \(vz\) are all non-edges of \(G\). The strong chromatic index \(s'(G)\) is the minimum number of colors in a strong edge-coloring of \(G\). Let \(G\) be a bipartite graph such that \(\Delta_1\) and \(\Delta_2\) are the maximum degrees among vertices in the two partite sets, respectively. A conjecture proposed by Brualdi and Quinn states that \(s'(G)\) is bounded by \(\Delta_1\Delta_2\). The author of this paper gives affirmative answer to this conjecture for the case \(\Delta_1=2\).