Θ-graphs of partial cubes and strong edge colorings

It was conjectured in [5] that the upper bound for the strong chromatic index s ′ ( G ) of bipartite graphs is Δ ( G ) 2 , where Δ ( 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 Θ-graph Θ ( G ) of a partial cube G, and show that s ′ ( G ) ⩽ χ ( Θ ( G ) ) for every tree-like partial cube G. As an application of this bound we derive that s ′ ( G ) ⩽ 2 Δ ( G ) if G is a p-expansion graph.