The Neighbor-distinguishing Edge Chromatic Number And Total Chromatic Number Of Graphs

Graph coloring problem is an important branch of graph theory,which originated from the famous " Four Color Problem".Graph coloring theory has been widely applied to computer science and wireless network and other fieldsLet NG(v)and NG(u)denote the sets of neighbors of v and u in G.A proper edge k-coloring 0 of a graph G is called a neighbor-distinguishing edge k-coloring,if C?(u)is not equal to C?(v)for any edge uv ? E(G),where C?(v)={?(vx)|x ? NG(v)}and C?(u)={?(uy)|y?NG(u)}.The neighbor-distinguishing edge chromatic number(hereinafter referred as the NDE-chromatic number)of G,denoted by ?'a(G),is defined to be the smallest integer k such that G has a neighbor-distinguishing edge k-coloring.In 2002,Zhang et al.introduced the neighbor-distinguishing edge coloring and conjectured that:If G is a connected graph with order at least 3 and G? C5,then ?'a(G)??(G)+2.A proper total k-coloring ? of a graph G is called a neighbor-distinguishing total k-coloring,if C?(u)is not equal to C?(v)for any edge uv ? E(G),where C?(v)={?(v)} ? {?(vx)|x ? NG(v)} and C?(u)={?(u)}? {?(uy)|y?NG(u)}.The neighbor-distinguishing total chromatic number(hereinafter referred to as the AVDT-chromatic number)of G,denoted by xa"(G),is defined to be the smallest integer k such that G has a neighbor-distinguishing total k-coloring.In 2005,Zhang et al.firstly introduced the neighbor-distinguishing total coloring of graphs and proposed the following conjecture If G is a connected graph with order at least 2,then ?"a(G)??(G)+In this master thesis,we shall investigate coloring problems of NDE-chromatic num-ber and AVDT-chromatic number.This thesis is divided into three chapters In Chapter 1,we introduce some basic concepts and notations that will be usedfrequently throughout the thesis.Then we present a chief survey in those directions and later we state the main results obtained In Chapter 2,we characterize the NDE-chromatic number of planar graph with?(G)? 14 by showing the following result:If G is a planar graph with ?(G)? 14,then?"a(G)=?(G)+ if and only if G contains two adjacent ?(G)-vertices.This improves a known result that gives a characterization on the planar graphs with ?(G)? 16,due to Zhang and HuangIn Chapter 3,we give a characterization for some planar graphs G to have the AVDT-chromatic number ?(G)+ or ?(G)+.More precisely,we show the following results:(1)If G is a planar graph with ?(G)=12,then ?"a)=14 if and only if G contains two adjacent 12-vertices.(2)If G is a planar graph with ?(G)=11,then ?"a)=13 if and only if G contains two adjacent 11-vertices.Our results are an extension to the currently known results obtained by Wang and Huang,and Huo et al.