The Strong Chromatic Index of Complete Halin Graphs

The 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. In this paper, we prove the following two theorems: (1) If G=T∪C is a complete Halin graph with Δ=4 that contains adjacent vertices of maximum degree, then χs′(G)≤χs′(T)+1=2Δ. In particular, when T is a regular tree, χs′(G)=χs′(T)+1=2Δ. (2) If G=T∪C is a complete Halin graph with Δ≥5 and G≠Wn, then χs′(G)=χs′(T)=2Δ−1 when T is a regular tree. We extend the strong edge coloring results for complete cubic regular Halin graphs studied by W.C. Shiu and W.K. Tam, and improve the upper bound on the strong chromatic index of general Halin graphs established by Wei Yang and Baoyindureng Wu.