Coloring Problems Of Graphs Via The Discharging Method

Graph coloring is an important ?eld in Graph theory. It has wide applicationsin modern computer science and information science. In this thesis, we are interestedin various coloring problems of graphs, including acyclic list coloring, star coloring,injective coloring, vertex-arboricity, fractional coloring and edge-face coloring. Themain method we will use in this thesis is Discharging argument.In Chapter 1, we collect some basic notions used in the thesis and give a chiefsurvey in each direction. Our main results will be stated.In Chapter 2, we mainly consider the acyclic list coloring of planar graphs. Thisnotion was ?rstly introduced （2002） by Borodin, Fon-Der Flaass, Kostochka, Raspaud,and Sopena. They proved that every planar graph is acyclically 7-list colorable. More-over, they proposed a challenging conjecture: every planar graph is acyclically 5-listcolorable. We will, in Chapter 2, show our result which is the best approach to thisconjecture. In addition, we obtain some su?cient conditions for planar graphs to beacyclically 3-list colorable or acyclically 4-list colorable.In Chapter 3, we focus on the star chromatic number of subcubic graphs. Bya more complex analysis of the structure of subcubic graphs, we prove that everysubcubic graph is 6-star-colorable. This result is best possible, since Fertin, Raspaudand Reed showed that the Wagner graph cannot be 5-star-colorable.In Chapter 4, we will investigate the injective chromatic number of K4-minor-free graphs. A vertex coloring of G is called injective, if every vertex v∈V , allthe neighbors of v are assigned with distinct colors. We shall prove that every non- empty K₄-minor-free graph G hasχi（G）≤32（G）, whereχi（G） denotes the injectivechromatic number of G. This result is best possible when （G） even in the sense thatthere exist K4-minor-free graphs G withχi（G） = 23（G）. Moreover, we will show ageneral upper bound on injective colorings of planar graphs.The vertex-arboricity va（G） of a graph G is the minimum number of subsets intowhich vertex set V （G） can be partitioned so that each subsets induces a forest. Re-cently, studying vertex-arboricity of graphs becomes a very popular topic. In Chapter5, we completely solved a conjecture of Raspaud and Wang asserting that every planargraph without intersecting triangles has vertex-arboricity at most 2.In Chapter 6, we will give the fractional chromatic number of sparse graphs bystudying the homomorphism problems of sparse graphs to the Petersen graph. Moreprecisely, we prove that every triangle-free graph with maximum average degree lessthan 5/2 is （5, 2）-colorable. Moreover, we show that the conditions“triangle-free”and“maximum average degree less than 5/2”are necessary.Finally, in Chapter 7, we will discuss the edge-face coloring of planar graphs. In2001, Sanders and Zhao proposed a challenge conjecture: every planar graph G is edge-face （（G） + 2）-colorable, and left the case∈{4, 5, 6} unsolved. In this chapter, weshall settle the case （G） = 6.