图的分解是图论的一个重要研究课题,其应用领域包括图的染色问题、大规模集成电路设计、计算机科学等.2012年,Montassier,Ossona de Mendez,Raspaud,and Zhu提出了著名的九龙树猜想:对于任意非负整数k和d,若Γf>(G)≤k+d/k+d+1,其中G的分数荫度Γf(G)=max H(?)G,v(H)>1e(H)/v(H)-1,那么G可分解为k+1个森林其中一个森林最大度不超过d.最近,蒋和杨证明了此猜想是正确的.我们称每个分支里最多只含有一个圈的图为伪森林.范、李、宋和杨证明了如下与九龙树猜想类似的伪森林分解定理:对于任意非负整数k和d,若mad(G)≤ 2k+2d/k+d+1,其中G的最大平均度mad(G)=max H(?)G 2e(H)/v(H)(?)那么G可分解为k + 1个伪森林其中一个伪森林最大度不超过d.本文在前人的研究基础上,进一步研究了伪森林分解及其在染色问题上的应用.本文由以下4章组成:第一章,我们介绍了文中需要用到的一些基本定义符号以及相关问题的研究现状.最后给出本文的主要结果.第二章,受九龙树猜想证明方法的启发,我们用新的阐述版本证明了上文中的伪森林分解定理,并得到一个稍强的结果:对于任意非负整数k和d,若mad(G)≤2k+2d/k+d+1,那么G可分解为k+ 1个伪森林其中一个伪森林最大度不超过d,且这个伪森林可分解为t个更小的伪森林F1,F2,...,Ft其中Fi最大度不超过di,且d =d1 + d2 +...+ dt.第三章,我们研究了伪森林分解在平方图染色及线图的平方图染色中的应用,并证明了:对于任意正整数k和d,若mad(G)≤ 2k 2d/k+d+1,那么col(G2)≤(2k + 2d-1)△ + k2 + 2k-d2 + 1 且col(L2(G))≤(4k+ 4d)△-2k-2d2-1.第四章,我们研究了线图的平方图的非对称博弈染色且定义了图的秩序这一概念.本章证明了:给定一个mad(G)≤ 2k秩序为r的的图G,若1≤a ≤2k△-k-1,则图G的(a,1)-博弈染色数不超过(2k + 1)△ +[(1 + 1/a)]-k;否则,(a,1)-博弈染色数不超过4k△-2k.特别地,当G是一个弦图时,若1 ≤ a ≤2k△-k-1,则图G的(a,1)-博弈染色数不超过(2k + 1)△ +[(1 + 1/a)r]-k,其中r =(△-2)k2 + 3k△-k-1.