On Improper Colorings Of Sparse Graphs

The study of graph coloring, which started from the famous Four Color Conjecture, has a central position in graph theory. Graph coloring has interesting real-life applications in optimization, computer science, network design and so on. The aim of this thesis is to discuss the improper coloring of sparse graphs.Letφ be a mapping from the vertex set V(G) of a graph G to the color set {1,2, … , k}, and let d1,… ,dk be the nonnegative integers. The coloring φ is an improper (d1,d2, …,dk)-coloring of G if the graph G[Vi] induced by the vertex subset Vi colored with i, has maximum degree at most di for each 1≤ i≤ k. Obviously, if d1= d2= …= dk= 0, then φ is a proper k-coloring of G. The maximum average degree of a graph G, denoted by mad(G), is the maximum value among the average degree of all subgraphs of G. Generally, we use the maximum average degree to measure the sparseness of graphs. A graph G is a sparse graph if its maximum average degree is a constant.The improper coloring of sparse graphs has been studied widely. In 2006, Havet and Sereni showed that every graph G with maximum average degree less than 4k+4/k+2 is improperly (k, k)-colorable. In 2010, Borodin et al. proved that every graph G with maximum average degree smaller than 3k+4/k+2 is (k, 0)-colorable. In this paper, we mainly discuss the (4,0)-coloring and (k,0,0)-coloring of sparse graphs, and improved the Borodin’s result.The 3-coloring of planar graph is a hot issue in the study of coloring problems of planar graphs. The famous Grotzsch’s theorem states that every triangle-free planar graph is 3-colorable. In 1976, Steinberg posed the following essential conjecture:every planar graph without 4- and 5-cycles is 3-colorable. Recently, Wang et al. proved that planar graphs without 4- and 6-cycles are (3,0,0)-colorable and (1,1,0)-colorable.In this thesis, we focus on the improper coloring of sparse graphs and planar graphs. Our work is constructed in three chapters. In Chapter 1, a short but relatively complete introduction is given by two sections. Firstly, we present some basic definitions and notations. Then the history of improper coloring is introduced. Finally, the main results of this thesis is outlined. In Chapter 2, we investigate the improper coloring of sparse graphs, and obtain the following theorems:Theorem 1. If G is a graph with maximum average degree at most 14/5, then G is (4,0)-colorable.Theorem 2. If G is a graph with maximum average degree at most 4k+9/k+3, then G is (k,0,0)-colorable.In addition, we construct graphs to verify that the bound on maximum aver-age degree in Theorem 1 is tight. Moreover, we construct non-(k,0,0)-colorable graphs whose maximum average degree are 12k+14/3k+4.In Chapter 3, we devote lots of effort to the improper coloring of planar graphs and prove the following theorem:Theorem 3. Let G be a planar graph without cycles of length 4 and 5. If G has no intersecting triangles, then G is (2,0,0)-colorable.