2-Distance Coloring Of Graphs

In this paper, all graphs are graphs without parallel edges and loop. Let Δ(G),δ(G) and dG(u,v) denote vertex set, edge set, maximum degree, minimum degree and the distance between u and v in G respectively.Call a graph G planar if it can be embedded in the Euclidean plane such that any two edges intersect only at their ends. Any such particular drawing of a planar graph is called a plane graph. For a plane graph G, we use F(G) to denote its face set. For ienotes the degree of x in G, simply d(x).The k-2-distance coloring of a graph G is a mapping uch that The 2-distance chromatic number χ2(G) is the smallest integer k such that G has a k-2-distance coloring.L(1,1)-labeling of G is a mapping uch that for every pair u Similarly,λp,q(G) is called the L(p, g)-labeling of G.A list assignment of G is a mapping L that assigns a list L(v) colors to each vertex v ∈ V(G). Given a list assignment L of G, a 2-distance coloring c of G is called a L-2-distance coloring if c(v) ∈ L(v) for each vertex v ∈ V(G). A graph G is fc-2-distance choosable if G has an L-2-distance coloring for any list assignment L with\L(v)\> k for each vertex v ∈ V(G). The 2-distance choice number of G, denoted by ch2(G), is the least integer k such that G is k-2-distance choosable.This master thesis, consisting of four chapters, focuses on 2-distance (list) coloring on the condition of without short cycles for graphs. In the first chapter, we introduce some definitions and give a brief survey of 2-distance (list) coloring. In the second chapter, we mainly discuss 2-distance coloring of a planar graph without 3,4,7-cycles. In the third chapter, we study the 2-distance coloring of planar graphs without short cycles. In the fourth chapter, we study some sufficient conditions for the L-2-distance coloring of a graph.