Strong chromatic index of bipartite graphs

Abstract

An edge-coloring of a graph $G$ is called a strong edge-coloring if all its color classes are induced matchings in $G$; the minimum number of colors required for such a coloring, denoted by ${\chi }_s^{\prime }(G)$, is known as the strong chromatic index of $G$. For each vertex $v$ of a graph $G$, let $d_G(v)$ denote the degree of $v$ in $G$. Let $G$ be a bipartite graph with partite sets $A$ and $B$, and let ${\Delta }_A=\max \{d_G(a):a\in A\}$ and ${\Delta }_B=\max \{d_G(b):b\in B\}$. A conjecture of Brualdi and Quinn Massey asserts that \( χ_s'(G) \le Δ_A Δ_B\). In this paper, we show that \(χ_s'(G) \le 1.676\, Δ_A Δ_B\) provided that the product ${\Delta }_A{\Delta }_B$ is sufficiently large.