Some Topics On Restricted Coloring Problems Of Graphs

The study of graph theory started over two hundreds years ago.The earliest known paper is due to Euler(1736) about the seven bridges of K(o|¨)nigsberg.Since 1960s,graph theory has developed very fast and numerous results on graph theory sprung forth.Graph coloring theory has a central position in graph theory. Graph coloring has interesting real-life applications in optimization,computer science and network design,such as file transfers in a computer network,computation of Hessians matrix and so on.The aim of this thesis is to discuss some topics on restricted coloring of graphs,such as acyclic coloring,total coloring,list coloring and f-coloring.In the thesis,all graphs considered are finite and simple.Let G be a graph with vertex set V(G) and edge set E(G).A proper total-k-coloring of a graph G is a coloring of V(G)∪E(G) using k colors such that no two adjacent or incident elements receive the same color.The total chromatic number x″(G) is the smallest integer k such that G has a total-k-coloring.The chromatic number x(G) of G and the edge chromatic number(or chromatic index) x′(G) of G are defined similarly in terms of coloring vertices alone,or edges alone,respectively.A proper vertex(or edge) coloring of a graph G is called acyclic if there is no 2-colored cycle in G.In other words,if the union of any two color classes induces a subgraph of G which is a forest.The acyclic chromatic number of G,denoted by a(G),is the least number of colors in an acyclic vertex coloring of G.The acyclic edge chromatic number of G,denoted by a′(G),is the least number of colors in an acyclic edge coloring of G.Let L be a list assignment which assigns a list L(v) of possible colors to each vertex v∈V(G).A graph G is acyclically L-colorable if there is an acyclic coloringφof the vertices such thatφ(v)∈L(v) for all v∈V(G). If G is acyclically L-colorable for any list assignment L with |L(v)|≥k for all v∈V(G),then G is acyclically k-choosable.Acyclic coloring problems are specialized coloring problems that arise in the efficient computation of Hessians matrix using automatic differentiation or finite differencing,when both sparsity and symmetry are exploited.In 2001,Alon,Sudakov and Zaks gave the following conjecture.Conjecture 1.a′(G)≤Δ(G)+2 for all graphs G.Some results on this conjecture are given in this thesis.For total coloring problems,Behzad and Vizing posed independently the famous conjecture,known as the Total Coloring Conjecture:Conjecture 2.For any graph G,Δ(G)+1≤x″(G)≤Δ(G)+2.This conjecture has been unsolved completely.For planar graphs G,the conjecture has been confirmed whenΔ(G)≠6.But for embedded graphs,it is often possible to determine x″(G) precisely.Another topic discussed in this thesis is list coloring.The mapping L is said to be a total assignment for the graph G if it assigns a list L(x) of possible colors to each element x∈V(G)∪E(G).If G has a total coloringφsuch thatφ(x)∈L(x) for all x∈V(G)∪E(G),then we say that G is total-L-colorable.Let f:V(G)∪E(G)→N be a function into the positive integers.We say that G is total-f-choosable if it is total-L-colorable for every total assignment L satisfying |L(x)|= f(x) for all elements x∈V(G)∪E(G).The list total chromatic number x″_l(G) of G is the smallest integer k such that G is totally-f-choosable when f(x)=k for each x∈V(G)∪E(G).The list chromatic number x_l(G) of G and the list edge chromatic number(or list chromatic index) x′_l(G) of G are defined similarly in terms of coloring vertices alone,or edges alone,respectively.List colorings were introduced by Vizing and independently by Erd(o|¨)s,Rubin, and Taylor.Part(a) of the following conjecture was formulated independently by Vizing,by Gupta,by Albertson and Collins,and by Bollobas and Harris,and it is well known as the List Coloring Conjecture and part(b) was formulated by Borodin,Kostochka and Woodall.Conjecture 3.If G is a multigraph,then (a)x′_l(G)=x′(G),(b) x″_l(G)=x″(G).There are only few results about Conjecture 3.The well-known Vizing's Theorem on the edge coloring asserts that,every simple graph G of maximum degreeΔ(G) hasΔ(G)≤x′(G)≤Δ(G)+1.Combining Vizing's Theorem and Total Coloring Conjecture,the following conjecture is obvious.Conjecture 4.For any graph G,we have (a) x′_l(G)≤Δ(G)+1,(b) x″_l(G)≤Δ(G)+2.For any simple graph G,we have x′(G)=Δ(G) orΔ(G)+1 by Vizing's Theorem.With this result,all simple graphs are naturally partitioned into two classes.We say that a graph G is of class 1 if x′(G)=Δ(G),and of class 2 otherwise.In 1986,Hakimi and Kariv generalized the proper edge coloring to the f-coloring and obtained many interesting results.Let f be a function that assigns a positive integer f(v) to each vertex v∈V(G).An f-coloring of G is a coloring of edges such that each vertex v has at most f(v) incident edges colored with the same color.The minimum number of colors needed to f-color G is called the f-chromatic index of G and is denoted by x_f(G).If f(v)=1 for all v∈V(G),then the f-coloring problem reduces to the classical edge coloring problem.LetΔ_f(G)=max{「d(v)/f(v)」:v∈V(G)}.Hakimi and Kariv showed that:Δ_f(G)≤x′_f(G)≤Δ_f(G)+1 for any graph G.Naturally,we say that graph G is of f-class 1 if x′_f(G)=Δ_f(G) and of f-class 2 otherwise.A graph G is called f-critical if G is of f-class 2 and x′_f(G-e)＜x′_f(G) for any edge e∈E(G).This thesis is concerned with some topics on restricted coloring of graphs. More specifically,our aim is to discuss acyclic coloring,total coloring,list coloring and f-coloring of graphs.We have constructed our work in five chapters.A short but relatively complete introduction is given in Chapter 1.First,we give some basic definitions and notations.Then we describe some definitions and history of restricted coloring which we consider in this thesis.At last,we outline the main results of this thesis.In Chapter 2,we investigate the acyclic edge coloring and acyclic list coloring of graphs.In the first time,we considered the acyclic edge colorings of graphs by combining method and partial coloring extension technique.An lower bound on acyclic edge chromatic number of planar graphs are given in Section 2.2.This results is better than the one given by Alon et al..We also consider the acyclic edge chromatic number of outerplanar graphs.It is the first subclass of which the acyclic edge chromatic number can be determined completely,except trees,or other trivial graphs as far as we know.At last,we consider acyclic list coloring of toroidal graphs and show that every toroidal graph is acyclically 8-choosable.In Chapter 3,we are interested in total coloring of graphs.We show that the total chromatic number of any graph G embedded in a surface∑of Euler characteristic x(∑)≥0 isΔ(G)+1 ifΔ(G)≥10.The proof of this result is simpler and may be used to do more things.We also consider the planar graphs without cycles of specific length and get many interesting results.In Chapter 4,we discuss the list coloring of planar graphs,including list edge coloring and list total coloring.At first,some results on Conjecture 4 are given. Then we consider list edge and list total coloring of planar graphs without 4-cycles and get some results on Conjecture 3.The main focus of Chapter 5 is to consider the f-coloring of graphs.Some properties of f-critical graphs are given.Then we consider the bound on the number of edges of f-critical graphs.At last,we introduce some other edge coloring problems.In addition,we present some unsolved problems in Chapters 2,3,4,5,respectively.