Adjacent Vertex Distinguishing Edge Colorings Of Planar Graphs

The coloring of graph has been an important and active branch in graph theory research. In this thesis, we investigate the adjacent vertex distinguishing edge colorings of planar graphs. This concept is the generalization of the traditional edge coloring, and has significant applications in the Frequency Channel Assignment and other Problems.Let△(G)(for short△) and g(G) denote the maximum degree, the girth of a given graph G, respectively. The proper edge coloring of graph G is called adjacent vertex distinguishing edge coloring, if any two adjacent vertices in graph G admit distinct color set. The adjacent vertex distinguishing chromatic index, denoted by x’a(G),is the smallest integer k such that G has a k-adjacent vertex distinguishing-coloring. Simi-larly, we can define the weak adjacent vertex distinguishing chromatic index, denoted by x’a△(G).This thesis consists of four chapters, In Chapter1, we introduce some concepts and notation used in the thesis, and give a chief survey on the recent progress of adjacent vertex distinguishing edge coloring.In Chapter2, we study the adjacent vertex distinguishing edge coloring of graphs with girth at least four. It is proved that if G is a normal planar graph with g(G)>4and△>6, then X’a(G)<△+2.In Chapter3, we show that the adjacent vertex distinguishing edge coloring con-jecture which was proposed by Zhang et al. is true for planar graphs with g(G)>5.In Chapter4, we study the weak adjacent vertex distinguishing edge coloring of graphs.(i)It is proved that if G is a planar graph with△≥9,then X’a△(G)≤△+2.(ii)It is proved that if G is a planar graph with△≥13,then X’a△(G)≤△+1.