On the strong chromatic index of cubic Halin graphs

AbstractA strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if they are incident to a common edge or share an endpoint. The strong chromatic index of a graph G, denoted by sχ′(G), is the minimum number of colors needed for a strong edge coloring of G. A Halin graph G is a plane graph constructed from a tree without vertices of degree two by connecting all leaves through a cycle. If a cubic Halin graph G is different from two particular graphs Ne2 and Ne4, then we prove sχ′(G)⩽7. This solves a conjecture proposed in W.C. Shiu, W.K. Tam, The strong chromatic index of complete cubic Halin graphs, Appl. Math. Lett. 22 (2009) 754–758