The Vertex Coloring Of Some Special Graphs

Graph theory is one of the most important branches in modern mathematics. The graph coloring problem comes from the famous Four Color Theorem, that is to say, if we want to color a map in plane satisfies two countries have different colors if they have one common side, we need four colors at most([1-3]). Later, some learners extend plane graphs to 1-planar graphs. A graph G called a 1-planar graph if it can be drawn on the plane that each edge is crossed by at most one other edge. In 1984, Bordin proved that 1-planar graphs are 6-colorable. In 1976, Steinberg came up a conjecture:Plane graphs without cycles of length 4 or 5 is 3-colorable. In order to prove steinberg’s conjecture, many scholars generalized the the proper coloring to improper coloring. Xu proved if a plane graph without cycles of length neither 4 nor 5 is (1,1,0)-colorable. Hill proved planar graphs without 4-cycles or 5-cycles are (3,0,0)-colorable. Wang proved planar graphs with cycles of length neither 4 nor 6 are (2,0,0)-colorable. Chang studied Steinberg’s Conjecture and near-colorings. In 1986, L. Cowen put up defective coloring of plane graphs.The vertex coloring is a partition of the vertices of G. If the vertex set can be partitioned into k parts which disjoint each other, we can give a proper color to each part so that it can meet some certain requirements, we call it a vertex coloring of G. When the subgraph induced by every part is independent set, the graph coloring of G is called a proper coloring. Otherwise, we call it improper coloring of G. If we put restrictions on the vertices of the induced subgraphs of G, such that the degree of all vertex in subgraph G[Vi] are di at most, then we call the graph G is (d1, d2, …,dk)-colorable. A k-coloring of graph G is that to color the graph G we need k colors at least, we also call graph G is k-colorable.For the proper coloring of G, we have these known results as follows: (1)[Four Color Theorem] Every plane graph is 4-colorable; (2) Every 1-planar graph is 6-colorable ([4]); (3) [Steinberg’s Conjecture] Every plane graph without cycles of length neither 4 nor 5 is 3-colorable; (4)If G is a plane graph without cycles of length 4,5,6,7, then G is 3-colorable ([13]); (5)If G is a plane graph without cycles of length 4,5,6,8, then G is 3-colorable ([14]); (6)If G is a plane graph without cycles of length 4,5,6,9, then G is 3-colorable ([15]); (7)If G is a plane graph without cycles of length 4,5,7,8, then G is 3-colorable ([16]); (8)If G is a plane graph without cycles of length 4,6,7,8, then G is 3-colorable ([17]); (9)If G is a plane graph without cycles of length 4,6,8,9, then G is 3-colorable ([18]); (10) If G is a plane graph without cycles of length 4,7,8,9, then G is 3-colorable ([19]);If we put restrictions on the vertices of the induced subgraphs of G, the proper vertex coloring turned to be improper coloring, we have the following classic results: (1) Every planar graph with cycles of length neither 4 nor 5 is (1,1,0)-colorable ([6]); (2) Planar graphs without 4-cycles or 5-cycles are (3,0,0)-colorable ([7]); (3) Planar graphs without 4-cycles or 6-cycles are (1,1,0)-colorable ([8]); (4) Planar graphs with cycles of length neither 4 nor 6 are (2,0,0)-colorable ([10]);According to the research about the vertex coloring of graphs, I follow in the footsteps of the previous scholars, continue to study the coloring problems.In the first chapter, we not only introduce some concepts, terminology and symbols we will use in this article, but also the background of this article and some existing results.In chapter 2, we consider the traditional proper vertex coloring problems, but we extend the traditional proper vertex coloring research in plane graphs to the study of 1-planar graphs. Bordin proved every 1-planar graph is 6-colorable. In this paper, we consider 1-planar graphs without 4-cycles or adjacent 5-vertices and obtain the following result:Theorem 1. If G is a 1-planar graph satisfies:(1) G contains no cycles of length 4;(2) 5-vertex is not adjacent to 5-vertex;then G is 5-colorable.Theorem 1 is about the 1-planar proper vertex coloring without 4-cycles or adjacent 5-vert ices, we induced the number of color from 6 to 5. We use the the Euler formula in plane graphs to prove it by design proper discharge rules.In the third chapter, we extend the traditional vertex coloring research in plane graphs to the study of 1-planar graphs, from proper vertex coloring to defective ver-tex coloring with some limits on every part. Inspired by X. Luo, M. Chen, Wang and other scholars in reference [17] [18] [19], we mainly consider the defective vertex coloring without cycles of length 3,4,5 in 1-planar graphs and obtain the following result:Theorem 2.1-planar graphs without cycles of length 3,4,5 are (1,1,1,1)-colorable.Theorem 2 extend the traditional proper vertex coloring in plane graphs to the study of defective vertex coloring of 1-planar graphs and the requirement for the part from independent sets to the degree of the vertex is at most 1. As a result, the number of color from 6 induced to 4.In the fourth chapter, We put forward a new improper vertex coloring problem in 2014. In this kind of improper vertex coloring, we don’t put limits on the vertex degree. But we require that each subgraph induced by every part contains no cycles of length l. Based on the discussions in chapter 2,3, it is not hard to find that in the research of graph coloring, we often need to limit some certain length cycles, so our new problem have some certain meaning.Definition:If graph G= (V,E) is a infinite graph, give a color distribution to the vertices of graph G such that each subgraph induced by every color set con-tains no cycles of length l, the minimum number of the color we need is called the cl-free chromatic number, denoted by Xct-f(G).In this paper, we consider the improper vertex coloring that each part contains no cycles of length 3 or 4 when the maximum degree is small. We get the following results:Theorem 3.When△≤4 and G≠K5,we have χc3-f(G)≤2.Theorem 4.When△≤4,we have χc4-f(G)=2.