图与超图的单色子图覆盖及相关问题

The Problem of monochromatic subgraphs covers in an edge-colored graph or hypergraph is a very improtant extremal combinatorial problem. In an r-edge-colored graph (or hypergraph) H, how many monochromatic subgraphs are needed to cover the vertices of H? In this project, we will study some problems in this field. (1) Monochromatic path covers and cycle covers in r-colored complete graphs. (2) Monochromatic path covers and cycle covers in r-colored non-complete host graph, such as complete bipartite graphs, host graphs with large minimum degree and orthogonal graphs; (3) other monochromatic subgraphs in r-colored complete graphs, such as monochromatic trees and regular graphs ; (4) Monochromatic path covers and cycle covers in k-uniform hypergraphs.

图与超图的单色子图覆盖问题是一类重要的极值组合问题，主要研究将一个图(超图)的边集用 r 种颜色染色后(这样的图称为r-着色图)，其顶点集的单色子图覆盖数。本项目围绕相关问题展开，拟研究以下问题：（1）r-着色完全图的单色路覆盖与单色圈覆盖问题；（2）r-着色非完全图的单色路覆盖与单色圈覆盖问题，如完全二部图，最小度限制图，平面图，正交图等的单色子图覆盖问题；（3）r-着色完全图的其他单色子图覆盖问题，如单色树覆盖，单色正则子图覆盖等；（4）k一致超图的单色路覆盖与单色圈覆盖问题。

本项目主要考虑涉及单色圈覆盖、单色路覆盖等的一些未解决问题。利用结构分析方法、有限域以及概率方法得到了R(C4，K1,n)一些新的值，并对R(C4,…,C4,K1,n)的上下界进行了估计，得到了R(C4,K1,m,Pn)的两个上界。用结构分析方法得到了R(Tn,Ws,4)以及R(Tn,Ws,5)的值。证明了当G的独立数等于2时，Erdös-Sós猜想和Loebl-Komlós-Sós猜想是正确的。完全确定了PR(Km,Tn)的准确值, 这是与Chvátal的经典的结论R(Km,Tn)相对应的平面Ramsey数版本。确定了不含4圈的平面图的最小度的最大值，并在此基础完全确定了PR(C4,Wn)的准确值。完全确定了PR(C4,Tn)的值。证明了每一个不含4圈和6圈的平面图都是(7:2)可着色的。研究邻和可区分全染色数和图点色数、边色数、及最大度的关系，得到了邻和可区分全染色数的两个上界。研究了2-生成图类中邻和可区分色指标和最大度之间的关系，推广了若干已有的结果。给出了连通图的与阶数和最小度有关的离心连通度的下界，刻画了达到下界的极值图。刻画了具有给定度序列的n阶树中具有最大离心连通度和最小离心连通度的极值图。还对一圈图给出了基于阶数和半径的离心连通度的下界，并刻画了达到下界的极值图。研究了度和条件下的控制圈问题，得到了一个最长圈是控制圈的度和条件。