| This dissertation is devoted to study the graph coloring problems.The coloring of graphs is one of the significant branches in graph theory.With their wide applications in reality,some new coloring concepts,such as equitable coloring,list coloring,vertex=distinguishing edge(or total) coloring,have come forth in the latest decades.Since it is NP=complete to determine the vertex(or edge) chromatic number of a general graph,it is also NP-complete to determine these generalized chromatic numbers.Thus,researchers mainly focus on some special classes of graphs and their various coloring problems.This dissertation consists of five chapters.Edge coloring,vertex distinguishing edge coloring,equitable coloring,equitable list coloring for planar graphs without some special configurations are investigated.In Chapter 1,we introduce some definitions and notations used throughout this dissertation,and give a chief survey on graph coloring problems under consideration.In Chapter 2,we discuss the edge coloring of graphs.The well-known Vizing's Theorem on the edge coloring says that every simple graph G has△≤x'(G)≤△+1,where△denotes the maximum degree of G.A graph G is of Class 1 if X'(G)=△and of Class 2 if x'(G)=△+1.In 1965,Vizing showed that every planar graph G with△≥8 is of Class 1 and conjectured that the conclusion holds for 6≤△≤7.The case△=7 was verified independently by Sanders and Zhao and Zhang.Thus,this conjecture remains open only for the△=6 case.In this chapter we prove that every planar graph G with△=6 is of Class 1 if it does not contain either a 4-cycle with a chord,or a 5-and 6-cycle with a chord,or a 6-cycle. Moreover,we deal with the edge-face coloring of some plane graphs.In Chapter 3,we consider the vertex-distinguishing edge coloring of graphs, which comes from non-regular networks.In 1997,Bun'is and Schelp,and independently Cerry and Homak,introduced this concept.In 2000,Zhang Zhongfu et ai.gave a weaker version,i.e.,adjacent strong vertex distinguishing edge coloring, and conjectured that if G is a connected simple graph with at least three vertices and different from a 5-cycle,then x'a(G)≤△+2.The conjecture was confirmed for a few special graphs such as trees,Halin graphs,bipartite.graphs,graphs with maximum degree 3,outerplanar graphs with maximum degree 4.In this chapter,we prove the following results:(1) If G is a planar graph without isolated edges and with girth at least 6,then x'a(G)≤△+2;(2) If G is a graph of order at least 5 with△=4 and without isolated edges,then x'α(G)≤8.In Chapter 4,we investigate the equitable coloring of graphs.In 1970,Hajnal and Szemerédi proved a conjecture by Erd(?)s in 1964,which states that every graph G has an equitable(k+1)-coloring for any integer k≥△.In 1973,Meyer conjectured that every connected graph G,which is neither a complete graph nor odd cycle,has x?(G)≤△.In 2003,Kostochka,Pelsmajer and West introduced the list equitable coloring of graphs and conjectured that every graph G is equitable k-choosable whenever k≥△+1.In this chapter,we consider the equitable coloring and the equitable list colorings of planar graphs without either 4- and 7- cycle,or 4-and 6-cycles,or 5- and 6-cycles.Chapter 5 is devoted to study the chromatic choosable graphs.A graph G is called to be chromatic choosable if its chromatic number is equal to its choice number.Galvin proved that the line graph of a bipartite graph is chromatic choosable. Ohba proved that if |V(G)|≤x(G)+(2x(G))1/2,then G is chromatic choosable. Recently,Reed and sudakov showed that G is chromatic choosable whenever |V(G)|≤5/3x(G)-4/3.We discuss this problem for 4-regular graph Hn.
|
PDF Full Text Request