Adjacent Vertex Distinguishing Edge And Total Colorings Of Graphs

The coloring of graph has been an important and active branch in graph theory research at all times.In this thesis,we investigate the adjacent vertex distinguishing edge and total colorings of some graphs.Both concepts are an interesting generalization of ordinary edge coloring and total coloring of a graph,which have significant applications in the Frequency Channel Assignment and other problems.Letχ′_α(G),χ″_α(G),Δ(G),g(G) denote the adjacent vertex distinguishing edge chromatic number,the adjacent vertex distinguishing total chromatic number,the maximum degree,the girth of a graph G,respectively.This thesis consists of five chapters.In Chapter 1,we introduce some concepts and notation used in the thesis,and give a chief survey on the recent progress of colorings under consideration.In Chapter 2,we characterize completely the adjacent vertex distinguishing total chromatic number of outerplanar graphs by showing that if G is an outerplanar graph withΔ(G)≥3,thenΔ(G) + 1≤χ″_α(G)≤Δ(G)+ 2,andχ″_α(G)=Δ(G) + 2 if and only if G contains two adjacent vertices of maximum degree.In Chapter 3,we study the adjacent vertex distinguishing total coloring of graphs with the maximum average degree less than 3.As a corollary,we determine the adjacent vertex distinguishing total chromatic number of planar graphs G with g(G)≥6 andΔ(G)≥5.In Chapter 4,we study the adjacent vertex distinguishing edge coloring of graphs with the maximum average degree less than 3.One of our results implies a characterization for planar graphs G with g(G)≥10 andΔ(G)≥5 according to their adjacent vertex distinguishing edge chromatic numbers.In Chapter 5,we study the adjacent vertex distinguishing edge coloring of K₄-minor-free graphs.It is proved that if G is a K₄-minor-free graph withΔ(G)≥5,thenΔ(G)≤χ′_α(G)≤Δ(G) + 1,andχ′_α(G) =Δ(G) + 1 if and only if G contains two adjacent vertices of maximum degree.