Adjacent Vertex Distinguishing Coloring And Vertex Arboricity Of Planar Graphs

Graph coloring theory has a center position in graph theory. It originated from the famous "Four Color Problem". Graph coloring has important applications in opti-mization, computer science, and network design etc.For a graph G, we use V(G) and E(G) to denote the vertex set and edge set of G, respectively. Let VE(G)=V(G)∪E(G), and call an element of VE(G) the element of G. A total k-coloring of a graph G is a map φ:VE(G)â†'{1.2,..., k}. A total κ-coloring of G is proper, if it satisfies any two adjacent or incident elements of G have different colors. A total chromatic number of G, denoted by χ"(G). is the least integer k such that G has a proper total κ-coloring. Similarly, we can define proper vertex coloring or proper edge coloring of G, respectively. We use χ(G) and χ’(G) to denote the vertex chromatic number and edge chromatic number of G, respectively.We consider some colorings with some constraints in this dissertation. A total coloring (not necessary proper) is called general neighbor distinguishing total coloring or gndt-coloring, if any two adjacent vertices have the different color sets. A gndt-chromatic number of G, denoted as gndt(G), is the least number of colors that G has a gndt-coloring. For a κ-gndt-coloring f, if/is proper, then f is called as κ-adjacent vertex distinguishing total coloring, or total κ-avd-coloring. The total avd-chromatic number of G, denoted as χa"(G),is least number of colors that G has a total avd-coloring. Similarly, we can define k-adjacent vertex distinguishing edge coloring, or κ-avd-coloring. The avd-chromatic chromatic index, denoted as χ’α(G), is the least integer k that G has a κ-avd-coloring. The vertex arboricity vα(G) of a graph G is the minimum number of colors the vertices can be colored so that each color class induces a forest. More specially, this dissertation is divided into four chapters, each of which is subdivided into.sections.Chapter1is devoted to providing a description of the history for the selected problems, and giving a statement of our main results.Chapter2is concerned with the total avd-coloring of graphs. Firstly, we study the general neighbor distinguishing total coloring of G, and give out a relationship between gndt(G) and χ(G). Secondly, we study the total avd-coloring of planar graphs. In2005, Zhang et al. conjectured that:if G is a connected graph with order at least2, then χ"α(G)≤△+3. We showed that the conjecture is true for planar graphs with maximum degree at least11. Lastly, we characterize completely the total avd-chromatic number of planar graphs with large maximum degree by showing that:if G is a planar graph with maximum degree△≥14, thenâ–³+1≤χ"α(G)≤△+2, and χα"(G)=â–³+2if and only if G contains two adjacent vertices of maximum degree.Chapter3is concerned with the avd-coloring of graphs. In2002, Zhang et al. conjectured that:if G is a connected graph with order at least3and G≠C5, then△≠χ’α(G)≤△+2. We show that the conjecture is true for planar graphs with maximum degree at least12.Chapter4is concerned with the vertex arboricity of graphs. It is well known that the vertex arboricity of any planar graph is at most3. And there exists a planar graph with vertex arboricity3. Hence, characterizing planar graphs G with uα(G)=2turned out to be one of the most interesting problems. In this chapter, we show that if G is a planar graph without7-cycles, or without chordal6-cycles, then uα(G)≤2.