$\mathrm{\Theta }$-Graphs of Partial Cubes and Strong Edge Colorings

Abstract

It was conjectured in $[10]$ that the upper bound for the strong chromatic index $s^{\prime }(G)$ of bipartite graphs is $\mathrm{\Delta }(G{)}^2+1$, where $\mathrm{\Delta }(G)$ is the largest degree of vertices in $G$. In this note we study the strong edge coloring of some classes of bipartite graphs that belong to the class of partial cubes. We introduce the concept of $\mathrm{\Theta }$-graph $\mathrm{\Theta }(G)$ of a partial cube $G$, and show that $s^{\prime }(G)\le \chi (\mathrm{\Theta }(G))$ for every tree-like partial cube $G$. As an application of this bound we derive that $s^{\prime }(G)\le 2\mathrm{\Delta }(G)$ if $G$ is a $p$-expansion graph.