Adjacent Vertex Distinguishing Edge Coloring Of Planar Graphs

Let G=(V,E)be a finite and simple graph,we use ?(G)?g(G)to denote the maximum degree and the girth of graph G,respectively.A graph G is normal if it contains no isolated edges.A proper edge k-coloring ? of G is adjacent vertex distinguishing(or in short a k-avd-coloring),if any two adjacent vertices has different set of colors.The adjacent vertex distinguishing chromatic index,denoted by ??'(G),is the smallest integer k such that G has a k-avd-coloring.The concept of adjacent vertex distinguishing edge coloring was introduced by Zhang et al..And they proposed the following conjecture:Let G be a normal connected graph and G ? C5,then ??'(G)??(G)+2 in 2002.Hatami showed that every normal graph G with ?(G)? 1020 has ??'(G)??(G)+300 by the probabilistic method.Balister et al.confirmed Conjecture for all bipartite graphs and graphs with ?(G)?3,and proved that for any normal graph G,??'(G)??(G)+O(log k),where k is the vertex chromatic number of G.Yan et al.showed that if G is a normal planar graph with girth g(G)? 5 and G?C5,then ??'(G)??(G)+2.Huang et al.showed that if G is a connected planar graph without 3-cycles and maximum degree at least 12,then ??'(G)??(G)+1.This paper is based on previous studies,and further discusses the adjacent vertex distinguishing chromatic index of the graphs,which is mainly divided into the following three parts:In Chapter 1,we introduce some basic definitions,a brief introduction about the research status of adjacent vertex distinguishing edge coloring,and the results we obtained in this paper.In Chapter 2 and 3,we study the adjacent vertex distinguishing chromatic index of planar graphs without short cycles.We first study the structural properties of the minimal counterexample,and use discharging methods to show our results.More precisely,we shall prove the following two results:(1)Let G be a normal planar graph without 4-cycles.Then ??'(G)?max{9,?(G)+1}.(2)Let G be a normal planar graph without 3-cycles.(2.1)Let T(G)=max{10,?(G)+1},then ?a'a(G)?T(G).(2.2)If ?(G)?10,then ?a'(G)=?(G)+1 if and only if G contains two adjacent?(G)-vertices.In Chapter 4,we used discharging method to study the adjacent vertex distinguishing chromatic index of planar graphs with large girth.That is,we prove the following result:(3)Let G be a normal planar graph with g(G)? 5.Then ?a'(G)?max{8,?(G)+1}.