图的群染色的研究

The purpose of this project is to investigate the properties of group coloring of graphs. We will investigate the relation between group colorability and the structure of groups, concerning both Abelian groups and non-Abeliangourps. We will work on the sufficient and necessary conditions for group perfect graphs, which would start from line graphs and claw-free graphs. We would use Erd?s-Rényi model to solve group coloring problems by random method, and hopefully identify critical complete bipartite graphs on group coloring by Lovász local lemma. Finally, group colorability of multigraphs are considered, especially for planar multigraphs, K3,3-minor free or K5-minor free multigraphs. Related algorithms to these problems are also under consideration.

本项目研究图的群染色性质及相关问题，主要研究群染色性质与群结构是否存在依赖关系，包括阿贝尔群和非阿贝尔群染色的区别和元素个数相同但不同构的群在染色上的等价关系；利用随机方法来研究群染色，主要包括在Erd?s-Rényi模型上刻画群染色与群列表染色以及利用Lovász局部引理研究多部图，特别是完全二部图的群染色情况；研究多重图与简单图的群染色性质的不同，重点关注多重平面图的群染色数与极图; 研究群完美图的结构，特别是线图和无爪图的群完美性。这些问题从算法上来讲，都是论是π2p -完全的，比NP-完全的(NP-complete)问题需要更多的计算和时间。因此是具有重要的理论意义和实际意义。它的研究将加深图的结构和参数研究，对群论、网络优化、密码学及计算机理论等方面也具有重要的理论价值。

染色问题是图论中一个重要的领域，拥有大量的难题和猜想。群染色是一般染色的一个推广。在项目研究中，我们研究了多重图的群染色问题，得到了多重图群染色版本的Brooks定理。我们同时对r-色调染色和(r,s)-正常图进行了研究。我们确定了无爪图的3色调染色数和列表3-色调染色数的上界。这表明除了一些无爪图是(3,4)-正常图外，其他所有的无爪图都是(3,3)-正常图。线图是研究图的结构时经常使用的方法。求一个图的线图可以看成一种作用在图上的运算。研究表明，大多数图的线图具有比原图更好的哈密顿性质。我们确定了图的泛圈连通因子，也就是最小的整数k，使得对图做k次线图运算，得到的图是泛圈连通的。在研究图的密度和利用线图研究图的哈密顿性质的时候，折叠图和超欧拉图是最常使用到的图类。我们将他们扩展到s折叠图和宽度为s的超欧拉图，并且证明了出类似折叠图的性质和定理，推广了折叠图的方法。