Pseudoforest Decompositions Of Graphs And Their Applications To Graph Colorings

Graph decomposition is an important research topic of graph theory.Its application fields include coloring problems of graphs,large scale integrated cir-cuit design,computer science and so on.The notable Nine Dragon Tree(NDT)Conjecture,which states that for any non-negative integers k and d,if Fr(G)?k + d/k+d+1,where fractional arboricity ?f(G)= max H(?)G,v(H)>e(H)/v(H)-1,then G decomposes into k + 1 forests with one having maximum degree at most d,was proposed by Montassier,Ossona de Mendez,Raspaud,and Zhu in 2012 and proven by Jiang and Yang recently.A pseudoforest is a graph with each com-ponent having at most one cycle.Similar to the NDT Conjecture,the theorem on the pseudoforest decompositions that for any non-negative integers k and d,if mad(G)? 2k+2d/k+d+1,where maximum average degree mad(G)= maxH(?)G 2e(H)/v(H),then G decomposes into k+1 pseudoforests with one having maximum degree at most d,was proven by Fan,Li,Song,and Yang.Based on the previous results,we make a further research on the pseudoforest decompositions of graphs and their applications to coloring problems.This thesis consists of the following four chapters:In chapter 1,we introduce the basic notations which will be used later and also the recent developments of the research in our concerned areas.Finally we give the main results of this thesis in this chapter.In chapter 2,we first prove the theorem on the pseudoforest decompositions mentioned above in a new version which is inspired by the method in the proof of the NDT Conjecture.And we obtain a slightly stronger result:for any non-negative integers k and d,if G is a graph with mad(G)?2k<2d/k+d+1,then G decomposes into k + 1 pseudoforests,where one of them is not only d-bounded but also can decompose into t smaller pseudoforests F1,F2,...,Ft such that each pseudoforest Fi has maximum degree at most d,and d = d1 + d2 +… + dt.In chapter 3,we study the applications of the pseudoforest decompositions to the coloring on the square of graphs and the square of line graphs.And we show that,for any positive integers k and d,if G is a graph with mad(G)?2k+2d/k+d+1,then col(G2)?(2k+ 2d-1)?+k2 +2k-d2 +1 and col(L2(G))?(4k + 4d)?-2k-2d2-1.In chapter 4,we study marking games on the square of line graphs.We give a definition of the rank of G,and we show that,for a given graph G with mad(G)? 2k and rank r,if 1 ? a ? 2k?-k-1,then(?,1)-gcol(L2(G))?(2k +1)?+ L(1+1/a)r]-k else if,(a,l)-gcol(L2(G))? 4k?-2k.Particularly,if G is a chordal graph with ?(G)? k+1,then for an integer 1 ? a ? 2f?-k-1,we have(a,1)-gcol(L2(G))?(2k + 1)?+[(1+1/a)r]-k,where r =(?-2)k2+3k?-k-1.