边染色图中彩虹匹配与染色圈的存在性研究

Edge-colored graphs can be viewed as a generalization of graphs and digraphs. This field not only contains many important problems and conjectures, but also has a wide application in Computer Science, Complex Networks and Bioinformatics. One of the most important subjects is about the existence of rainbow matchings and edge-colored cycles. In this project, we mainly investigate several extremal problems concerning the existence of rainbow matchings and edge-colored cycles, including three conjectures presented by Aharoni et al., rainbow Turan problems for matchings and the existence of rainbow matchings and edge-colored cycles under color degree constraint. We will give a profound characterization on the relationship between edge-colored graphs and digraphs, improve the color degree conditions guaranteeing the existence of rainbow matchings and edge-colored cycles, and resolve some important problems and conjectures using the probabilistic method, the algebraic method, rainbow Blow-up lemma, absorbing method and digraph theory. The project is closely related to digraph theory, combinatorial design and extremal combinatorics. Making progress on related problems will benefits the improvement and innovation of graph theory.

边染色图是对图和有向图的推广，该领域存在着许多重要的问题和猜想，并在计算机科学、复杂网络、生物信息学等领域有着重要的应用，彩虹匹配与染色圈的存在性问题是其重点研究内容之一。本课题将主要研究彩虹匹配与染色圈的几类极值问题，包括Aharoni等提出的三个猜想、匹配的彩虹Turan问题和色度条件下彩虹匹配与染色圈的存在性问题。我们将深入刻画有向图与边染色图之间的联系，改进彩虹匹配与染色圈存在的色度条件，并争取运用概率方法、代数方法、彩虹Blow-up引理、吸收引理、有向图理论等方法解决几个重要问题和猜想。本课题的研究与有向图理论、组合设计、极值组合等方向关系密切，相关问题的解决十分有利于图论本身的发展与创新。

本项目主要研究了边染色图和拟随机超图中的几个极值问题，与有向图理论、超图中的Turan问题等有密切联系，是图论领域近期的研究热点。本项目主要取得了以下成果：得到了不含彩虹完全二部图的边染色图的一个重要性质，从而得到了一些染色圈存在的色度条件；确定了强边染色图中彩虹Hamilton圈、彩虹Hamilton路以及彩虹完美匹配存在的最小度，解决了Cheng等人提出的猜想；改进了匹配的彩虹Turan数的相关结果，并提出了兼容性Turan问题，得到了完全图、奇圈等结构的兼容性Turan数的上下界；解决了Lenz和Mubayi所提出的F-因子问题中F为3一致超图或k部k一致超图的情况，并将此问题推广到其他拟随机性和度条件下加以研究，得到了一些结果。本项目的研究成果对染色子图的存在性问题以及拟随机超图中的F-因子问题的进一步研究提供了有效的思路。