图的某些重要参数的进一步拓展与应用研究

For a graph G,the parameters of maximum average degree of G, the fractional arboricity of G,and the coloring number of G, are well-known. These parameters have already attracted a lot of attention and have a lot of applications. The famous Nash-Williams Theorem states a necessary and sufficient condition for the bounded arboricity of graphs. Montassier, Ossona de Mendez, Raspaud,and Zhu proposed the Nine Dragon Tree (NDT) Conjecture, which is a refinement of the Nash-Williams theorem. Following this direction, we proposed a refinement to the Hakimi Theorem which is related to the maximum average degree of G. Since these parameters and theorems are very influctial, in this proposal, we plan to have some more advanced study on these parameters and their applications. We plan to use the new methodology that we have developed during our proof for the refinement of the Hakimi Theorem to study the Nine Dragon Tree (NDT) Conjecture. We shall also try to improve some currently known upper bounds of the chromatic number and game chromatic number of some classes of graphs by using the already refined forms of the parameters and theorems. In this proposal, we also plan to study the generalized coloring numbers, the game coloring numbers, and some other generalized parameters (such as the distance k-independence number, the distance k-domination number, etc) of graphs, we plan to study the interrelationships among these parameters, and the applications of the generalized parameters. For some important parameters, the algorithmic approach for some problems will also be studied.

图的最大平均度参数、图的分数荫度参数、以及图的染色数参数，在图论中有着非常广泛的应用。由Montassier,朱绪鼎教授等提出的"九龙树猜想" 是对图的分数荫度参数和Nash-Williams-Tutte关于图的森林分解的著名定理的精细化拓展。与此类似，我们对图的最大平均度参数和与之相关的Hakimi定理，进行了精细化拓展研究。有鉴于这些参数和定理的广泛影响力，本申请项目拟对这些参数与定理展开进一步的拓展与应用研究。用我们在对Hakimi定理的精细化研究中发现的一些新方法，对"九龙树猜想"展开研究。尝试用已经证明的定理的精细化形式，来改进某些图类现在已经证明的色数或博弈染色数的上界。本项目还拟研究图的一般染色数，图的博弈染色数, 以及其他推广后的参数（例如：距离k-独立数和距离k-控制数，等），研究这些参数之间的关系问题，以及推广后的参数的应用问题，并对某些重要参数的算法相关问题展开研究。

本国家自然科学基金面上项目“图的某些重要参数的进一步拓展与应用研究”主要计划研究图的最大平均度参数，图的分数荫度参数，图的染色数参数，由Montassier、朱绪鼎教授等提出的"九龙树猜想"，Nash-Williams、Tutte关于图的森林分解的定理的进一步拓展，等相关问题。本项目还计划研究图的一般染色数，图的博弈染色数, 以及其他推广后的参数（例如：距离k-独立数和距离k-控制数，等），研究这些参数之间的关系问题，以及推广后的参数的应用，等问题。..我们对项目课题，做了认真研究。对申请书中的计划研究内容，投入了巨大的时间和精力，全心全意认真工作，完成了计划研究任务。特别是对本项目的主要计划研究内容，也是很多图论学者广泛关注的“九龙树猜想”，在本国家自然科学基金面上项目的支持下，经过项目研究小组多年的不懈努力和不屈不挠的认真研究，我们完整彻底地解决了“九龙树猜想”。在对问题的研究和解决过程中，我们有了很多新的发现。我们即发现了一些新的技术和方法；也对一些经典结果的证明以及他们之间的内在联系，有了很多新的理解和推广。本项目的进行，取得了一系列的高水平科研成果。其中，尤其以“九龙树猜想”的彻底解决为代表的高水平系列研究成果，最为引人注目。在本项目的资助下，迄今为止，已经发表论文Journal of Combinatorial Theory, Series B（二篇）, Combinatorica（一篇）, Advances in Applied Mathematics（一篇），European Journal of Combinatorics（一篇）， Journal of Graph Theory（一篇）, Electronic Journal of Combinatorics（一篇）。还有一些研究成果正在审稿中，或正在整理待投稿。..本项目积极支持国内外学术合作交流。项目负责人以及某些项目组主要参加人员，参加了全国多次学术会议。 在本项目的支持下，我们也多次与国内的、国际的同行、其他图论研究团队，进行了形式多样的、非常积极的学术交流。本项目主持人在项目进行期间做过多次会议邀请报告，访问了捷克 Nesetril 院士。本项目的进行，还支持和培养了一大批硕士、博士研究生，这些研究生参与了原创性的、高水准的科研工作，这对他们的快速成长和科研能力的提高，构成了极大的帮助。