The Strong Edge Coloring Of One Class Of Halin Graphs

The edge coloring problem and its variations are important in graph theory. In this dissertation, we will discuss the strong edge coloring problem.Given a graph G=(V(G),E(G)), the strong edge coloring of a graph G is an assignment of colors to the edges of G, satisfying if two edges have the same endpoint or incident to a common edge, then the two edges are colored differently. The minimum number of colors needed for a strong edge coloring of G is called the strong chromatic index, denoted by sx’(G).A Halin graph G=T U C is a planar graph constructed from a characteristic tree T and an adjacent cycle C where T has at least4vertices and without vertices of degree two and C connects all the leaves of the tree. In this dissertation, we prove that sx’(G)≤9, where G=TU C is a Halin graph in which each vertex of T has degree4or1.