图的列表染色及相关问题研究

Graph coloring is an important field in graph theory. It has wide applications in information science, communication science, operational research and other fields. This direction has attracted more considerable attention in recent years. In this project, we are interested in various graph coloring problems which are popular in these years. First, we try to solve the BFKRS conjecture and the MRW conjecture concerning on acyclic list coloring of planar graphs. Secondly, characterize some new graph families which have vertex-arboricity 2. Thirdly, study list (1,1,1)-coloring. We try to provide some sufficient conditions for graphs which are to be list (1,1,1)-colorable. Also, we will discuss the (i,j,k)-colorability of sparse graphs and planar graphs with given girth. Fourthly, aiming at the famous Sanders-Zhao conjecture, we try to completely solve it, and extend some results about planar graphs to other graphs, i.e., toroidal graphs, Klein graphs, etc. Finally, we shall consider some other related coloring problems, e.g., star coloring, vertex-face coloring and entire coloring. We attempt to improve the upper bound and lower bound of star chromatic number of general planar graphs. Moreover, we shall study the Wang-Lih conjecture which says that every planar graph is vertex-face list 6-colorable and characterize the entire list chromatic number of special planar graphs. At least 20 papers are completed after the project being finished, where at least 15 papers are indexed by SCI.

图的染色理论在图论研究领域中一直占据着重要的地位，在信息科学、通讯科学、运筹学等领域有着广泛的应用，受到了国内外同行的密切关注。本项目旨在围绕几类图染色猜想，研究当前国际图论界的热点问题。首先，力争解决或部分解决BFKRS和MRW两大关于平面图无圈点列表染色猜想。其次，刻画具有点荫度为2的平面图类。然后，研究平面图列表(1,1,1)-染色，扩大满足Xu-Zhang猜测的图类，讨论具有围长限制的平面图和稀疏图的(i,j,k)-可染性。再有，在现有的基础上，争取彻底解决极具挑战的Sanders-Zhao边面染色猜想，推广平面图边面（列表）染色的一些结果到曲面图上去。最后，探讨其他一些染色问题，如星染色、点面染色和完备染色。改进平面图的星色数上界与下界，研究平面图6-点面列表染色猜想，精确求出某些特殊平面图的完备列表色数。拟在四年内完成学术论文20余篇，其中15以上发表在SCI源期刊上。

图的染色理论在图论研究领域中一直占据着重要的地位，在信息科学、通讯科学、运筹学等领域有着广泛的应用，受到了国内外同行的密切关注。本项目主要研究图的顶点列表染色（包括正常、非正常、无圈、限制性列表染色）、分解问题（荫度、顶点列表荫度、森林分解）以及边面染色等热点问题。研究围绕着相关领域的几个著名猜想（如Sanders-Zhao 猜想、Xu-Zhang 猜想、无圈顶点列表染色猜想）展开，致力于解决或部分解决这些猜想和难题，给出相关图参数好的上界或下界，对特殊图族（如平面图、环面图、稀疏图等）给出若干参数的精确值。解决了Sanders-Zhao 猜想剩余的两种情形之一，即证明了最大度为5的平面图是边面7-可染的。完全刻画了环面图列表顶点荫度。部分解决了MRW提出的关于平面图是无圈4-点列表可染的猜想。研究了列表顶点荫度至多为2的环面图类。找到了新的图类满足Xu-Zhang 猜想。给出了平面图3-点列表可染性以及4-点列表可染性的充分条件。对围长为5的平面图类，将已知的子图分解结果全部改进到森林分解。证明了九龙树猜想对k≤2的情形成立，此结果发表在Journal of Combinatorial Theory, Series B期刊上。四年内共发表挂有基金号的学术论文17篇，其中SCI检索15篇。