2-Distance Coloring Of Planar Graphs

Call a graph G planar if it can be drawn in the plane such that any two of its edges intersect only at their ends. All graphs in this paper are simple, finite and planar graphs. The k-2-distance coloring of a graph G is a mapping φ:V→{1,…, k} such that |φ(u) - φ(v)|≥ 1 if 0< dG(u, v)≤ 2. The 2-distance chromatic number X2(G) is the least k such that G has a k-2-distance coloring. The list 2-distance chromatic number of G is the least k such that for every list L of size k, G has a 2-distance coloringφ, φ(v) ∈ L(v) whenever v ∈ V(G), denoted by X2(G).The research of 2-distance coloring of planar graphs originated form Wegner’s conjecture which posed in his report in 1977:assume G is a planar graph, then (1) X2(G) ≤ 7 if △(G)= 3; (2) X2(G) ≤ △(G)+5 if 4 ≤ △(G) ≤ 7; (3) X2(G) ≤ [2/3△(G)]+1 if △(G)≥ 8. Wegner’s conjecture is still open. But sometimes tight upper bound of plane graphs’2-distance chromatic number can be proved. Wang and Cai proposed a problem:suppose G is a plane graph without 4-cycles, find the least t such that X2(G) ≤ △(G)+t.This paper focuses on 2-distance (list) coloring of planar graphs without short cycles. In the first chapter, we introduce some definitions and give a brief survey. In the second chapter, we mainly discuss list 2-distance coloring of planar graphs with g(G)≥ 5 and g(G)≥ 6. In the third chapter, we study the list 2-distance coloring of planar graphs without 4,5-cycles. In the fourth chapter, we study 2-distance coloring of planar graphs without 4-cycles.