广义列表着色的色可选性

As a restricted type of an ordinary (proper) vertex coloring, in the 1970s, Vizing and Erdös et al. independently introduced the concept of list coloring of a graph. Since then, a lot of variations and generalizations of list coloring such as improper list coloring, circular list coloring, online list coloring were introduced and have now become important branches in the field of graph coloring. It is known that the chromatic number is no greater than the list chromatic number of a graph and moreover, Erdös et al. showed that the difference between these two numbers could be arbitrary large for some graphs. In this sense, characterizing those graphs whose chromatic and list chromatic number are equal possesses particular significance both in theory and application. Such graphs are also called chromatic choosable. This project studies the chromatic choosability for some generalized list colorings. We focus on 1. Studying Ohba-type conjecture with respect to improper list coloring; 2. (a,b)-list choosability; 3. List choosability of graphs with particular interests. To implement the project, we try to apply and develop some known theory and method such as the theory of Combinatorial Nullstellensatz, the random graph theory and so on. The project is expected to enrich the theory of graph list colorings.

作为通常意义下图的（正常）点着色的一种变形，上世纪70年代，Vizing和Erdös等独立地提出了图的列表着色概念。其后，学者们引进了列表着色的许多变形与推广，如非正常列表着色，圆列表着色，在线列表着色等，列表着色现已成为图着色领域中的一个重要分支。易知图的色数不超过图的列表色数，事实上，Erdös等曾证明对于某些图类，这两者的差可以任意大。从这个意义上讲，刻画所谓色可选图类（即色数与列表着色相等）在理论和应用上都占据着重要的地位。本项目研究一些广义列表着色下的色可选性。重点研究 1.非正常列表着色意义下的Ohba型猜测； 2.(a:b)可选性；3.特殊图类的色可选性。为了实施本项目，申请者试图应用和发展已有的理论和方法，如组合零点定理，随机图理论等。项目的开展将丰富图的列表着色领域。

列表着色是图着色领域的热点研究问题，其中的一个关键问题就是所谓色可选性问题。本课题围绕列表着色的色可选性，主要研究内容有三个：(1).非正常着色的Ohba猜想以及超图Ohba猜想(2).列表着色函数与色多项式的关系问题(3).符号图的Alon-Tarsi数问题及Noel-Reed-Wu定理。得到的重要结果如下：.(1).对于d-非正常着色，证明了当G顶点数不超多(d+3/2)χ^d(G)+d/2时，G是d-非正常色可选的。 相关的结果发表在Graphs Combin.上。 作为经典Ohba猜想 (Noel-Reed-Wu定理) 的自然推广，对于任意正整数r≧2，提出了r-一致超图的Ohba型猜测: 对任意的r-一致超图，若|V(G)|≦rχ(G)+r-1,则G是色可选的。证明了这一猜想对于两类顶点数恰为rχ(G)+r-1的完全多部超图是成立的，通过构造两类顶点数恰为rχ(G)+r的非色可选的例子证明了所提出的超图Ohba猜想条件是紧的。相关结果发表在Electronic J Combin.上。.(2).从计数的角度研究列表着色，使用经典的Whitney破圈定理，证明了当列表大小k大于1.135倍的边数时，任意k列表分配对应的允许着色个数以常列表为最小。这一结果极大地改进了Donner和Thomassen之前得到的条件，发表在JCTB上。进一步地，运用超图的破圈定理，我们还将这一结论推广到一致超图上。研究过程中，我们还提出一种不依赖于序的容斥相消原理，发表在JCTA上。.(3).定义了符号图的Alon-Tarsi数及模p Alon-Tarsi数并将Alon-Tarsi列表着色定理推广至符号图. 证明了任何符号平面图的Alon-Tarsi数及模p Alon-Tarsi数至多是 5, 推广了朱在无符号平面图上的结论, 后者蕴含任何符号平面图是Z5-可着的. 发表在Graphs Combin.上。给出了Noel-Reed-Wu定理在符号图中的一个推广，结果被Discrete Math接收。. 项目组在项目执行期间得到的这些结果及提出的猜想一定程度上丰富和推进了图的列表着色领域，对后续的研究具有较强的参考价值。