多项式方法在图论中的应用

The polynomial method is a powerful tool in the study of many combinatorial problems and number theoretic problems. In this project, we concentrate on the application of this method to some graph theory problems, including anti-magic labeling of graphs, list coloring of graphs, online list coloring of graphs and total weight choosability of graphs. We aim at some long standing conjectures, including the anti-magic labeling conjecture, which states that every connected graph other than K2 has an antimagic labeling, the (1,3)-total weight choosability conjecture, which implies that every graph with no isolated edges has an edge weighting using weights 1,2,3 so that adajcent vertices have distinct vertex-sums，and some other conjectures. We shall also study the online choice number of families of graphs, and coloring and list coloring of graphs. We shall develop variations of polynomial method during the application of this method.

多项式方法在组合学和数论中有广泛地应用。本项目将研究多项式方法在图论研究中的应用，包括在图的anti-magic标号、列表染色、在线列表染色和图的点边赋权的研究中的应用。主要关注几个长期未解决的猜想，如anti-magic标号猜想：每一个连通的不等于K2的图存在anti-magic标号，（1,3）-点边列表赋权猜想：每个不含孤立边的图是（1,3）-列表可选的（该猜想可推出1-2-3猜想：每个不含孤立边的图有一个用1,2,3权重的边赋权使得相邻顶点的权重和不等。我们还将研究一些图类的在线选择数，以及图的染色和列表染色。在应用多项式方法于这些问题的同时，进一步发展这一方法。

多项式方法是图论研究的重要工具，本项研究计划一个要点是应用多项式方法于一些具体的图论问题以及研究多项式方法的推广。另一个要点是研究图的各类染色问题。本项目围绕上述方向，针对计划提出的问题开展研究。主要成果有：（1）证明平面图的Alon-Tarsi数最大为5。这一结果强化了Thomassen关于平面图5-可选的经典结果，解决了有Hefetz在《Journal of Combinatorial Theory Ser. B》上提出的公开问题（2）证明了每一个平面图G都含有一个匹配M, G-M的Alon-Tarsi数不超过4。这一结果推广了Cushing-Kierstead关于平面图1-defective 4-可选的结果，解决了平面图均可1-defective 在线4-可选的问题。这一问题Kierstead团队和我们都研究多年。（3）提出了augment rooted tree的概念，构造性证明了大围长augmented tree的存在性。Erdos利用概率方法证明了大色数大围长图的存在性。这是色数图论的经典结果。利用大围长augmented tree，我们给出了这一结果非常简洁的构造性证明，同时构造了大选择数大围长稀松二部图。Alon利用组合零点定理证明平均最大度数为2k-2的二部图是k-可选的。出乎人们意料，我们证明这一有关边数的条件是最优的。（4）研究了列表染色的精细化问题，提出了lambda-可选的概念，(k+epsilon)-可选的概念，广义符号图染色的概念和强分数选择数的概念。证明了平面图的最大强分数选择数不小于4+2/9， 无三角形的平面图的最大强分数选择数不小于3+1/17。 证明了每一个平面图都是 （4+1/2）-可选的。（5）研究了列表染色的一个推广-DP染色。研究了分数DP-色数的概念。刻画了分数DP-色数为2的图。证明了当顶点个数足够接近色数是，其DP-色数等于色数。得到了满足这一结论的顶点数的上界的级别（确切数仍然是一个未解决的问题）。.本项目也协助主办大型学术会议一次，中小型学术会议四次。邀请十多位学者来访，积极出访交流。.培养学生方面，有四位博士生，十位硕士生参与项目的研究。