The 2-distance Coloring Of Graphs

Let G be a graph,we use V(G),E(G),△(G),δ(G),g(G),mad(G)and d(u,v)to denote vertex set,edge set,maximum degree,minimum degree,girth,maximum average degree and the distance of u,v in G respectively.A k-2-distance coloring of graph G is a mapping φ:V(G)→ {1,2,···,k},such that any two vertices u,v satisfy 0<dG(u,v)≤2 hasφ(u)≠φ(v).We call a graph G is k-2-distance colorable if G has a k-2-distance coloring.The 2-distance chromatic number X2(G)is the least integer k such that G has a k-2-distance coloring.A list assignment of a graph G is a mapping L which assigns to each vertex v a set L(v)of positive integers.We say G is 2-distance L-colorable if there exists a proper vertex coloring c of G such that c(v)∈ L(v)for every u ∈V(G).A graph G is list 2-distance k-colorable if G is 2-distance L-colorable for every list assignment L with |L(v)|= k for all v ∈ V(G).We define X2l(G)= min{k|G admits a list 2-distance k-coloring} as the list 2-distance chromatic number of a graph G.The research of 2-distance coloring of graphs originated in 1977,Wegner proposed the following conjecture:for a plane graph G,(1)χ2(G)≤ 7 if △=3;(2)χ2(G)≤ △+ 5 if 4 ≤ △ ≤7;(3)χ2(G)≤[3/2△]+1 if △ ≥8.Wegner also presented that the upper bounds are tight if the conjecture is true.Wegner’s conjecture is still open.We can find a graph which has infinite 2-distance chromatic for arbitrary graphs.In 1993,Ramanathan proved that it is NP-hard to give the 2-distance chromatic number of a plane graph.Thus,the upper bounds of 2-distance chromatic number of a plane graphs are widely concerned by the scholars of graph theory.In this master thesis,we focus on 2-distance(list)coloring of simple graphs with maximum degree 5 and planar graphs without short cycles.The thesis consists of three chapters.In Chapter 1,we collect some basic notations,give a chief survey in this direction and state the main results obtained.In Chapter 2,we mainly discuss the list 2-distance coloring of simple graphs and obtain the following three results:(1)If G is a simple graph with △(G)= 5 and mad(G)<20/7,then χ2l(G)≤ 10.(2)If G is a simple graph with △(G)= 5 and mad(G)<19/6,then χ2l(G)≤ 11.(3)If G is a simple graph with △(G)= 5 and mad(G)<41/12,then χ2l(G)≤ 13.In Chapter 3,we study the 2-distance coloring of plane graphs by showing that every planar graph G with girth at least 5 and △≥ 44 has χ2(G)≤ △+4.