图的子图和染色

图的匹配、路和圈结构是图论中的基础而又重要的研究方向，也是图的因子理论，极值图论和Ramsey理论的研究重点。图的染色问题也是图论中的热门的研究课题。本课题主要研究图的子图和图的染色的关系，其中包括图的正交匹配和边染色图中的彩色匹配的关系，边染色图中的彩色圈和正常染色的圈的存在性问题，图的Ramesy数和anti-Ramsey数，以及有向图中的彩色路问题等。我们力求解决上述研究领域的几个难题和猜想，改进关于边染色图中的匹配、路和圈的存在性条件，深入刻画边染色图中的子图和染色之间的关系。本课题的研究涉及到矩阵理论，组合设计，超图理论等多个领域，问题的解决对计算机科学，生物数学及组合数学和图论的理论发展和创新都有非常重要的意义。

图的多色子图方面,我们得到了图的彩色匹配存在的色度条件，而且我们对图的正交匹配特别是Alspach猜想做了研究，得到了目前该问题的最好的界。同时，我们对Erdös-Bollobás关于边染色图中的正常染色圈的下界做了改进，得到了目前最好的界，为我们后续关于超图中的极值问题（特别是彩色匹配）打下了很好的基础。另外，我们对图的和可区别染色、图的无圈边染色等也做了研究。在对图的和可区别染色的研究中，我们除了借助于传统的discharging方法，还应用组合零点定理，结合MATLAB的计算，使我们在对一般图、平面图和几类特殊图的研究中分别取得了不错的结果。在对无圈边染色的研究中，利用熵压缩的方法，在推广的无圈边染色方面取得了一系列不错的成果。共发表SCI论文30余篇，多次在国内和国际会议上作报告。前三位申请人也都在此基础上获得了国家自然科学基金的资助。