Some Coloring Problems Of Planar Graphs

The coloring problem of graphs is a very important research subject in graph theory. The applications of graph coloring theory are very extensive. The graph coloring theory has important application in theoretical computer science, web design, combinatorial optimization, files transmission in a com-puter network, and so on. It also has a close relationship with our daily life. For example, many problems can be converted to graph coloring problem to be solved. Such as task scheduling, circuit layout, handling of chemicals storage, examination scheduling problem, curriculum and classroom arrange-ment and so on. According to the difference of rule or object, there are many kinds of colorings of graphs. The aim of this thesis is to discuss total coloring and vertex arboricity.All graphs considered in this thesis are finite, nonempty, undirected and simple. For a graph G=(V, E), we use V(G), E(G),δ(G), â–³(G) (or simply V, E, δ,â–³) to denote the vertex set, the edge set, the minimum degree and the maximum degree of G, respectively. If G is a planar graph, then denote by F(G) the face set of G. We use|V(G)|,|E(G)|,|F(G)|(or simple|V|,|E|,|F|) to denote the number of vertices, edges, faces, respectively. For a face f, the degree d(f) of f is the length of the boundary walk of f. Let d(v) denote the degree of v, that is, the number of vertices adjacent to v.In chapter 1, we give a relatively complete introduction for the develop-ment of coloring theory, total coloring and vertex arboricity. First, we give some basic definitions and notations. Second, we describe some definitions and notations of some coloring problems and introduce their histories, de-velopment, and list some associated conjectures and conclusions. Then, we explain the proof method and thought of this thesis. Last, we outline the main results of this thesis.In chapter 2, we study the total coloring of graphs, obtain three conclu-sions and give their proofs. For a graph G=(V, E), a proper k-total-coloring is a mapping φ:V ∪Eâ†'{1,2,...,k} such that no two adjacent or inci-dent elements receive the same color. A graph G is k-total-colorable if it admits a k-total-coloring. The total chromatic number χ"{G) of G is the smallest integer k such that G is k-total-colorable. Clearly, χ"(G)≥△A+1. Behzad and Vizing posed the famous conjecture independently, known as Total Coloring Conjecture:for any graph G, χ"(G)≤△+2. For planar graphs, the only open case is â–³= 6. Interestingly, the total chromatic num-ber of planar graphs with large maximum degree equals the lower bound,i.e., χ"(G)=â–³+1. Now, this result was extended to △≥9. In this thesis, we give some sufficient conditions on planar graphs with △≥7 to have total chromatic number â–³+1.The first conclusion of this chapter is:Let G be a planar graph with △≥7. If G does not contain chordal 7-cycles, then χ"(G)=â–³+1. The second conclusion of this chapter is:Suppose that G is a planar graph with â–³=7. If for each vertex v, there is an integer kv ∈{3,4,5,6,7,8} such that there is no kv-cycle which contains v, then χ"(G)=8. We also have a corollary:Suppose that G is a planar graph with △≥7. If for each vertex v, there is an integer kv ∈{3,4,5,6,7,8} such that there is no kv-cycle which contains v, then χ"(G)=â–³+1. The Euler’s formula we used is ∑v∈V(2d(v)-6)+∑f∈F(d(f)-6)=-12. Besides some known reducible configurations, we prove one new reducible configuration. The difficulty is how to define discharge rules, the charge be transferred is determined previous. In our discharge rules, the charge which transfer from vertices to incident 3-faces is flexible, since the determined charge is unable to give or not enough. We can give charge according to the situation by our discharge rules strictly. The advantage is that we need not give our discharge rules more detailed and can use the charge of vertices incident to 3-faces sufficiently. The last conclusion of this chapter is:Let G be a planar graph with △≥7. If G does not contain intersecting semi-chord 4-cycles, then χ"(G)=â–³+1. The Euler’s formula we used is ∑v∈V(d(v)-4)+∑f∈F{d(f)-4)=-8. Besides some known reducible configurations, we prove some new reducible configurations. The difficulty is that ch’(v)=0 in several places when we check the final charge of the maximum degree vertices. So we adjust discharge rules for several times.In Chapter 3, we consider the vertex arboricity of planar graphs. A forest k-coloring of a graph G is a mapping φ from the vertex set V(G) to the set{1,2,..., k} such that each color class induces an acyclic subgraph, i.e., a forest. The vertex arboricity va(G) of G is the smallest integer k such that G has a forest k-coloring. This version of vertex arboricity was first introduced by Chartrand et al. in 1968, who named it point-arboricity. Chartrand et al. pointed out that va(G)≤[1+â–³(G)/2] for any graph G and va(G)≤3 for any planar graph. The following year, Chartrand and Kronk showed this bound 3 is sharp. If give some restrictions on planar graphs, we can have vertex arboricity 2. In this thesis, we study the vertex arboricity of planar graphs. The first conclusion in this chapter is:If G is a planar graph without intersecting 5-cycles, then va(G)≤2. The difficulty is how to find reducible configurations and prove it. The second conclusion in this chapter is:Let G be a planar graph, if 3-cycle is not adjacent to 4-cycle and 5-cycle is not adjacent to 5-cycle, then va(G)≤2. The Euler formula we used in the two conclusions is ∑v∈V(2d(v)-6)+∑f∈F(d(f)-6)=-12.In chapter 4, we introduce some coloring of graphs relating with total coloring and vertex arboricity and introduce some other graphs. We pose some questions we need to consider and give the direction we want to con-tinue.