Strong edge-coloring of cubic bipartite graphs: A counterexample

A strong edge-coloring phi of a graph G assigns colors to edges of G such that phi(e(1)) not equal phi(e(2)) whenever e(1) and e(2) are at distance no more than 1. It is equivalent to a proper vertex coloring of the square of the line graph of G. In 1990 Faudree, Schelp, Gyarfas, and Tuza conjectured that if G is a bipartite graph with maximum degree 3 and sufficiently large girth, then G has a strong edge-coloring with at most 5 colors. In 2021 this conjecture was disproved by Luzar, Macajova, Skoviera, and Sotak. Here we give an alternative construction to disprove the conjecture. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This article presents a conjecture about strong edge-coloring of a graph and states that the conjecture was disproved in 2021. It also provides an alternative construction to disprove the conjecture.