Research On The Neighborhood R-Bounded Coloring Of Graphs

Graph coloring problem is always a central research area in combinatorial mathematics.As the extensions of classic vertex coloring problem,some graph coloring problems with vertex or edge constraints are being constantly introduced and have attained abundant results in the past two decades.Among all kinds of restricted graph coloring problems,though the neighborhood r-bounded coloring was introduced by Hind,Molloy and Reed in 1997,the research of neighborhood r-bounded coloring is spectacularly restricted up till now even if its definition was introduced such early.This thesis mainly surveys the problem of neighborhood r-bounded coloring of graphs.Following the research structure of all graph coloring problems,we firstly construct a neighborhood r-bounded coloring method of graphs by making use of the greedy algorithm and prove the Brooks’ type upper bound of neighborhood r-bounded chromatic number and discuss the graph classes that satisfy this chromatic upper bound;moreover,we also prove the property of graphs that satisty a more accurate upper bound.Planar graphs is an important graph class and has drawn great attention in other graph coloring problems,thus the thesis also turns to focus on the neighborhood r-bounded coloring of general planar graphs.For example,Cai,Xie and Yang in[6]obtained a structural property of planar graphs.On this basis,the thesis derives the neighborhood r-bounded chromatic number of planar graphs;next we introduce the neighborhood r-bounded chromatic upper bound conjecture based on the Wagner conjecture and other relevant restricted graph coloring problems.To certify the conjecture,we tend to discuss two important subclasses of planar graphs-outer-1-planar graphs and K₅^--minor free graphs.First,outer-1-planar graphs,as an important subclass of planar graphs,has drawn great attention recently.For example,Zhang and Li discussed all 17 possible local structures of outer-1-planar graphs in[33];Meanwhile,Liang,Liu and Lai in[21]extended the r-hued list chromatic number by using this structure property.Motivated by the above research,the thesis obtains the neighborhood r-bounded chromatic number of outer-1-planar graphs.Finally,we use the same proof method and provide the neighborhood r-bounded list chromatic number of K₅^--minor free graphs as a supplement of our research.