The Structures And Colorings Of Some Classes Of Topological Graphs

The study of graph coloring acts as one of the most important direction of graph theory since the raise of the well-known Four Color Problem in the middle of19th century. As it turned out, almost every mathematician on graph theory had investigated the colorings of graphs, and some of them dedicated their scien-tific lifetime to this colorful and interesting subject of graph theory:Chromatic Graph Theory. Graph coloring has interesting real-life applications in optimiza-tion, computer science and network design. Many practical problems, such as file transfers in a computer network and computation of Hessian matrix, can directly or indirectly transfer to graph coloring models and then can be solved by combina-torial method. The aim of this thesis is to investigate the structures and colorings of some classes of topological graphs, such as1-planar graphs, IC-planar graphs, pscudo-outcrplanar graphs and planar graphs.Every graph considered in this thesis is simple, undirected, finite and non-empty. We use V(G), E(G), F(G), δ(G) and△(G) to denote the vertex set, the edge set, the face set, the minimum degree and the maximum degree of a graph G, respectively. A planar graph is a graph that can be drawn on a plane so that there is no crossings. If a graph can be drawn on a plane so that each edge is crossed by at most one other edge, then we call it1-planar graph. Let G be an embedding of a graph on a plane. If there is a crossing in this embedding, then one can easily confirm that this crossing is generated by one edge crossing one other edge. Therefore, we can establish a relationship λ from a crossing to a set of four vertices, which are the end-vertices of the two crossed edges. Let a and b be two crossings of (the drawing of) G. If λ(a) n λ (b)=?, then we call that a, and b are independent. If a graph G can be drawn on a plane so that every two crossings are independent, then we call G IC-planar graph (this is the abbreviation of plane graph with independent crossings). A graph is pscudo-outcrplanar if each block has an embedding on the plane in such a way that the vertices lie on a fixed circle (this just means a geometrical circle) and the edges lie inside the disk of this circle with each of them crossing at most one another.1-planar graphs, IC-planar graphs, pscudo-outerplanar graphs and planar graphs arc the four classes of topological graphs we investigate in this thesis. The following is a basic relationship among those classes of topological graphs:1-planar graphs(?) IC-planar graphs(?) planar graphs(?)pscudo-outerplanar graphs. In this thesis we mainly study the chromatic structures of1-planar graphs, IC-planar graphs, pscudo-outerplanar graphs and planar graphs, and then we apply them to the coloring problems of those classes of graphs.Let G=(V, E) be a graph. A vertex t-coloring of G is a mapping c from its vertex set V to a set of colors{1,2,…, t}. If c(u)≠c(u) for every edge uv∈E, then we say that c is a proper vertex t-coloring of G and that G is t-colorable. The set of vertices that arc colored by a same color under c is called a color class. A proper vertex coloring of a simple graph G is κ-forested if the subgraph induced by the vertices of any two color classes is a κ-forest, i.e. a forest with maximum degree at most k. In this thesis, we would investigate the κ-forested coloring of planar graphs in Chapter5.Let c be proper vertex t-coloring of a graph G. If every two color classes of c differ by at most1, then we call c an equitable t-coloring of G. The smallest integer t such that G has an equitable t'-coloring for all t'≥t, denoted by χeq*(G), is called the equitable chromatic threshold of G. The well-known Chen-Lih-Wu Conjecture (also known as Equitable△-Coloring Conjecture) asserts that every connected graph G, except the complete graph Kr and the odd cycle C2m+1and the balanced complete bipartite graph K2m+1,2m+1satisfies χeq*(G)≤△(G). In this thesis we prove this conjecture for1-planar graphs with maximum degree at least17.Let G=(V, E) be a graph. An edge t-coloring of G is a mapping c from its edge set V to a set of colors{1,2,…,t,}. If every two adjacent edges in G receive different colors under c, then we call c a proper edge t-coloring of G and say that G is edge t-colorable. The smallest integer t such that G is edge t-colorable, denoted by χ'(G), is called the edge chromatic number of G. The well-known Vizing's theorem states that△(G)≤χ'(G)≤△(G)+1for every simple graph G. Thus, by the edge chromatic number we can divide all simple graphs into two classes. If X'(G)=△(G), then G is said to be of class1; if χ'(G)=△(G)+1, then G is said to be of class2. It is known that every planar graph with maximum degree at least7is of class1and there exists class2planar graph with maximum degree△for each△≤5. In this thesis we would investigate the edge colorings of another three classes of topological graphs; they are1-planar graphs, IC-planar graphs and pscudo-outcrplanar graphs.A proper edge coloring of G is r-acyclic if every cycle C contained in G is colored with at least min{|C|,r} colors. The r-acyclic edge chromatic number of a graph, denoted by ar'(G), is the minimum number of colors required to produce an r-acyclic edge coloring. In this thesis, we would investigate the r-acyclic edge coloring of planar graphs in Chapter5by proving that a4'(G)=O(△(G)) for every planar graph G.Let G=(V,E) be a graph. A total t-coloring of G is a mapping c from V U E to a set of colors{1,2,…, t}. If every two adjacent or incident elements in G receive different colors under c, then we call c a proper total t-coloring of G and say that G is totally t-colorable. The smallest integer t such that G is totally t-colorable, denoted by χ"(G), is the total chromatic number of G. Total Coloring Conjecture asserts that χ"(G)△≤(G)+2for every graph G. In this thesis we would prove this conjecture for1-planar graphs with maximum degree at least13.For every edge e∈E(G) of a graph G, we assign a set of colors L(e) to e and call L an edge list of G. If there exists a proper edge coloring c of G such that c(e)∈L(e) for every e∈E(G), then we call that G is edge L-colorable. If|L(e)|=t for every e∈E(G) and G is edge L-colorable, then we call that G is list edge t-colorable or edge t-choosable. The smallest integer t such that G is list edge t-colorable, denoted by χι'(G), is called the list edge chromatic number of G. The list total chromatic number χ"(G) can be defined similarly in terms of coloring both vertices and edges. The well-known List Coloring Conjecture asserts that χι'(G)=X'(G) and χι"(G)=χ"(G) hold for every simple graph G. This con-jecture is very difficult to be confirmed or disproved. A weaker conjecture, namely Weak List Coloring Conjecture, is still interesting and has also been extensively considered in the literature. This conjecture asserts that χι'(G)≤△(G)+1and χι"(G)<≤△(G)+2hold for every simple graph G. In this thesis we confirm List Coloring Conjecture for1-planar graphs with maximum degree at least20and IC-planar graphs with maximum degree at least14, and confirm Weak List Coloring Conjecture for1-planar graphs with maximum degree at least16and IC-planar graphs with maximum degree at least11.More specifically, our aim in this thesis is to investigate the chromatic struc-tures and the colorings of1-planar graphs, IC-planar graphs, pseudo-outerplanar graphs and planar graphs. We have constructed our work in six chapters.A short but relatively complete introduction is given in Chapter1. First, we give some basic definitions and notations. Then, we describe some necessary definitions and some relative conjectures that would be considered in the next chapters. At last, we outline the main results of this thesis.Chapter2is the main part of this thesis, where we investigate the chromatic structures and the colorings of1-planar graphs. In particular, we prove that every1-planar graph without chordal k-cycles and with maximum degree△is of class1if (△,k)∈{(7,3),(8,4),(9,5),(10,+∞)}. On the other hand, we construct class21-planar graphs with maximum degree△for each△∈{2,3,4,5,6,7}. Furthermore, the well-known Total Coloring Conjecture, List Coloring Conjecture, Weak List Coloring Conjecture and the Equitable△-Coloring Conjecture are confirmed for1-planar graphs with large maximum degree in this chapter.In Chapter3, we study the structures and colorings of IC-planar graphs. First of all, we show that every IC-planar graph is6-dcgcnerate. Then, we gen-erate this proposition to three stronger structural theorems. By applying these structural results, we prove that every IC-planar graph with maximum degree at least8is of class1. Moreover, we confirm List Coloring Conjecture for IC-planar graphs with maximum degree at least△and girth at least g, where (△,g)∈{(14,3),(8,4),(7,5)}. In Chapter4, we mainly work with pseudo-outerplanar graphs, which is a new class of topological graphs introduced by the author. In this chapter we first consider some basic properties of pseudo-outerplanar graphs, and then study the edge decomposition problems of pseudo-outerplanar graphs. In particular, we prove that each pscudo-outcrplanar graph admits edge decompositions into a linear for-est and an outerplanar graph, or a star forest and an outerplanar graph, or two forests and a matching, moreover, we also claim that the above ways of edge de-compositions arc optimal in some sense. At last, by establishing17unavoidable but reducible configurations of any pseudo-outerplanar graph, we prove that the edge chromatic number of every pseudo-outerplanar graph with maximum degree at least4is, and the linear arboricity of every pseudo-outerplanar graph with maximum degree3or at least5is exactly [△/2], moreover, two classes of extremal pseudo-outcrplanar graphs arc presented there to show that those bounds on the maximum degree are sharp.In Chapter5, we first investigate the κ-forested coloring of planar graphs. In particular, we prove that the κ-forested chromatic number of every planar graph G with maximum degree at least△and girth at least g is exactly[△(G)/κ]-1if (△, g)∈{(κ+1,10),(2κ+1,8),(4κ+1,7)} and κ>3, or (△,g)=(κ+1,8) and κ≥7. On the other hand, we study the r-acyclic edge coloring of planar graphs by proving that α4'(G)=O(△(G)) for every planar graph G and aτ'(G)=△(G) for every planar graph with maximum degree at least Υ and girth at least5Υ+1.In Chapter6, we propose some interesting problems for further research to end this thesis.