2-Distance Coloring Of Graphs

All graphs considered in this paper are finite simple graphs. The2-distance k-coloring of a graph G is a mapping c:V(G)â†'{1,2,···,k} such that c(u)≠c(v) for every pair of vertices u and v satisfying0<dG(u, v)<2. We define x2(G)=min{k|G admits a2-distance k-coloring} as the2-distance chromatic number of a graph G.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 is2-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 list2-distance k-colorable if G is2-distance L-colorable for every list assignment L with|L(v)|=k for all u∈V(G). We define x2l(G)=min{k|G admits a list2-distance k-coloring} as the list2-distance chromatic number of a graph G.About the2-distance coloring of planar graphs, in1977, Wegner posed the follow-ing conjecture:for a planar graph G, if Δ(G)=3, then X2(G)≤7; if4≤Δ(G)≤7, then X2(G)≤Δ(G)+5; if Δ(G)≥8, then x2(G)≤[3/2Δ(G)]+1.This paper consists three chapters and mainly study the2-distance coloring of pla-nar graphs without special short cycles and graphs with maximum degree not more than5. In the first chapter, we introduce some basic definitions and the research sta-tus of2-distance coloring, and gives the results of this paper. In the second chapter, we mainly study the2-distance coloring of planar graphs without special short cycles, proving that (1) If G is a planar graph without3-,4-,8-cycles and with Δ(G)>14, then X2(G)≤Δ(G)+5.(2) If G is a planar graph with Δ(G)≥12which contains no3-,5-cycles and intersecting4-cycles, thenx2l(G)≤Δ+6. In the third chapter, we mainly study the2-distance coloring of graphs with maximum degree not more than5, showing that (1) If G is a planar graph with Δ(G)<5and mad(G)<18/7, then X2l(G)≤7.(2) If G is a planar graph with Δ(G)≤5, then the following results hold:1) if g(G)≥5, then x2l(G)<13;2) if g(G)≥6, then X2l(G)≤11;3) if g(G)≥7, then x2l(G)≤9;4) if g(G)>8, then x2l(G)≤8.