On The Coloring Of Halin Graphs

The coloring theory of graph is one of the most important components of graph theory, it is also one of the origin of graph theory. For hundred years, it has been attracting the mathematicians deeply. Nowadays, it has very important application in many domains. For example, the production management, military, the transportation, the computer network and so on. Halin graph is one kind of special planar graph;it is R. Halin that proposed in 1969 as minimum 3-connected graph. As a result of its own special structure, in recent years, the coloring on Halin graph has become a hot topic in the coloring theory of graph.What we study and discuss in this paper are three kinds of coloring problem of Halin graphs—the adjacent strong edge coloring, the vertex strong total coloring and the strong coloring.First, in this paper, an algorithm for vertex strong total coloring of wheel is given. Meanwhile, an effective coloring method on the vertex strong total coloring of Halin Graphs—the method of coloring cycles one by one is presented. We can finish the vertex strong total coloring of Halin Graphs by using this method in polynomial time. Meanwhile, the bounds of vertex strong total chromatic number of Halin graphs with Δ(G) = 3 are given. The upper bound and the lower bound is 6 and 5, respectively. We also determine the strong chromatic number and vertex strong total chromatic number of Ne_h, and the corresponding coloring scheme is given meanwhile. And then, we present a coloring method on the strong coloring of Halin graphs with Δ(G) = 3.Second, we give a concise proof for the adjacent strong edge chromatic theorem of Halin graphs in [11]. With the illumination of the coloring method on the strong coloring of Halin graphs with Δ(G) = 3, a coloring method on the adjacent strong edge coloring of Halin graphs with Δ(G) = 3 is presented. Recur to the tool of 1-factor, we get that the upper bound of the adjacent strong edge chromatic number of Halin graphs with Δ(G) = 3 is 5 and the lower bound is 4. At the end of this paper, we give a sufficient condition of X_as' (G) = Δ +1 for Halin graphs with Δ(G) ≥ 4.