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.