【作者】 陈敏；

【导师】 王维凡； André Raspaud；

【作者基本信息】 苏州大学 ， 运筹学与控制论， 2011， 博士

【摘要】 图的染色是图论研究的重要内容,在现代计算机科学、信息科学等领域有着十分广泛的的应用,一直得到国内外同行的极大关注.本学位论文主要围绕着图的六大染色问题展开,即:无圈点列表染色、星染色、Injective染色、点荫度、分数染色以及边面全染色.除了分析探讨图的自身结构之外,我们主要运用著名的Discharging方法来研究平面图的染色问题.在第一章,我们给出本文所用到的基本概念,简述了相关领域的研究现状,并给出本文的主要结果.在第二章,我们着重研究平面图的无圈点列表染色问题.此类问题最早（2002）是由Borodin, Fon-Der Flaass, Kostochka, Raspaud和Sopena引入和研究的.他们证明了每个平面图是无圈7-点列表可染的,并且提出了极具挑战性的猜想:每个平面图是无圈5-点列表可染的.我们在第二章中给出目前最接近此猜想的结果,并且还得到了平面图无圈3-点列表染色以及4-点列表染色的充分条件.在第三章,我们将集中精力研究Subcubic图的星色数.利用对Subcubic图的结构分析,我们证明了:每个Subcubic图是6-星-可染的.需要说明的是:这个结果是最好可能的,因为Fertin, Raspaud和Reed已经给出了Wagner图不是5-星-可染的结论.在第四章,我们将主要探讨K₄-minor-free图的Injective色数问题.图G的点染色被称作是Injective的,如果任意点v的邻点颜色互不相同.我们将证明:每个非空的K4-minor-free图G的Injective色数最多是-32-（G）-.此结果,当-（G）为偶数时,是最好可能的,因为存在一个非空的K4-minor-free图H（-（H）为偶数）的Injective色数恰好为-23-（H）-.另外,我们还给出了一般平面图的Injective色数上界.一个非平凡图G的点荫度va（G）是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林.近年来,图的点荫度问题的研究成为图论的一个焦点.在第五章,我们将完全解决Raspaud和Wang提出的猜想:每个不包含相交三角形的平面图的点荫度最多是2.在第六章,我们将通过研究Sparse图与Petersen图的同构关系来讨论Sparse图的分数染色.证明了每个无3-圈且最大平均度小于5/2的图是（5,2）-可染色的.我们将通过反例说明:条件“无3-圈”和“最大平均度小于5/2”都是必不可少的.最后,在第七章,我们讨论了平面图的边面全染色问题. 2001年, Sanders和Zhao提出了极具挑战性的猜想:每个平面图G是（（?）（G） + 2）-边面全染色的,并且先后解决了（?）≥7和（?）≤3的情况.迄今为止, （?）∈{4,5,6}的情形仍然是开放的.作为本学位论文的亮点之一,我们彻底解决了（?）（G） = 6的情况.更多还原

【Abstract】 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.更多还原