关于几类图的分数色数与独立数

Graph coloring theory is a classic problem in the research of graph theory because of its theoretical and practical significance. It has important applications in combinatorial optimization, transportation flow, network design and computer science, etc. Vertex coloring is one of the most important branches of graph coloring, and fractional coloring is a natural generalization of vertex coloring of graphs. Since the fractional chromatic number is a lower bound of its vertex chromatic number of any graph, it is interesting to study the fractional chromatic number of graphs. Note that the product of the independence number and fractional chromatic number is no less than the order of a graph, we can get a lower bound of the independence number of a graph by its upper bound of fractional chromatic number. The independence number of a graph has a close relationship with Ramsey theory. All research contents of this project are as follows: the fractional chromatic number and independence number of graphs related to three color problems, the independence number of four-cycle-free (planar) graphs and the bounds of (planar) Ramsey number for four-cycle versus complete graphs, the fractional chromatic number and independence number of graphs without subdivisions of K5. As a result, the project will contribute to the earlier solution to the three color problems, improve the bounds of (planar) Ramsey number for four-cycle versus complete graphs and generalize the fractional coloring of planar graphs.

图的染色理论是图论研究的一个热点，它在组合最优化、交通流、网络设计和计算机理论等方面有着广泛的应用。顶点染色是图的染色理论中的一个主要内容，分数染色是顶点染色的一种推广。由于图的分数色数是顶点色数的一个下界，研究图的分数色数对于我们更进一步地研究图的顶点色数有着重要的意义。此外，由于图的独立数不小于其阶数与分数色数的比值，我们可以通过研究图的分数色数，来研究图的独立数。图的独立数与Ramsey理论有着紧密的联系。本项目拟采用权转移、线性规划、组合和概率等方法研究与三色问题有关的分数染色与最大独立集问题，不含4圈的(平面)图的独立数与4圈对完全图的(平面)Ramsey数，不含K5细分的图的分数色数与独立数。这些问题的解决，不仅可以从另一角度推进三色问题的验证工作，而且可以改进4圈对完全图的(平面)Ramsey数的界，推广平面图的分数染色的结果，从而丰富和完善图的染色理论和Ramsey理论。

本项目中，通过构造一个(4:1)-可选的但不是(8:2)-可选的图，否定了Erdős-Rubin-Taylor猜想(每个(a:b)-可选图都是(ka:kb)-可选的)。通过对图的结构性质的刻画，利用图的hyperbolicity理论证明了任意给定曲面Σ上只存在有限多个围长为5的(3a:a)-临界图，推广了Thomassen等人的工作。在此基础上，证明了对于最大度为Δ，围长为5的平面图G，存在M∆，使得其分数色数不超过3-3/(2M∆+1)。在分数染色方面，我们还证明了不含4圈或5圈的平面图是(11:3)-可选的，从而其分数色数不超过11/3，独立数至少为3|V(G)|/11；不含4圈或6圈的平面图(7:2)-可染的，从而其分数色数不超过7/2，独立数至少为2|V(G)|/7。图的限制条件的染色问题方面，用颜色交换的技术确定了图的邻点可区别全色数新的上界；通过刻画2-退化图的子图结构，确定了其邻和可区别边色数。结合极值图论的方法，证明了当图的独立数为2时，Erdős-Sós猜想和Loebl-Komlós-Sós猜想成立；确定了4圈对树的平面Ramsey数；证明了毛毛虫的燃烧数的上界，确定了几类特殊毛毛虫的燃烧数。针对网络图的结构，研究了某些具有应用背景的网络的容错性和匹配性。