Improper Coloring Of 1-planar Graphs

We consider only finite, simple and undirected graphs in this paper.Let d1,…,dk be k nonnegative integers. A graph G = (V, E) is called improp-erly (d1,…, dk)-colorable, or just(d1,…,dk)-colorable,if the vertex set V can be partitioned into subsets V1,…,Vk, such that the graph G[Vi] induced by the ver-tices of Vi has maximum degree at most di for all 1 ? i ? k. This notion generalizes those of proper k-coloring (when di = …?dk = 0).A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. The notion of 1-planar graphs was introduced by Ringel,and he conjectured that each 1-planar graph is 6-colorable. It was confirmed by Borodin in 1986. Since there exists a 7-regular 1-planar graph, the bound 6 is sharp. In 2005, it showed that it is NP-complete to decide whether a given 1-planar graph is (0,0,0,0)-colorable.As the extension of proper coloring of graphs, improper coloring has been s-tudied extensively. In 1976, Steinberg proposed that every planar graph with cycles of length neither 4 nor 5 is (0,0,0)-colorable. Motivated by Steinberg's conjecture,many known results are obtained. For example, every planar graph with neither 4-cycles nor 5-cycles is (2,1,0)- and (4,0,0)-colorable.In this paper, we extend the improper coloring of planar graphs to the 1-planar graphs. Inspired by the improper coloring of planar graphs, we mainly discuss the improper coloring of 1-planar graphs with girth at least 7. In Chapter 1, we introduce some definitions, and give a brief survey of 1-planar graphs and improper coloring of planar graphs. In Chapter 2 and Chapter 3, we assume that a 1-planar graph G has been embedded on a plane such that every edge is crossed by at most one other edge. The associated plane graph G* of a 1-planar graph G is the plane graph obtained from G by turning each crossing of G into a new 4-vertex, called a crossing vertex. According to the construction and properties of 1-planar graph G and its associated plane graph G*, we proved that 1-planar graphs with girth at least 7 are (1,1,1,0)- and (2,0,0,0)-colorable,respectively.