边染色图中的异色子图问题

边染色图中的异色子图（路、圈、匹配、树等）问题是当代图论研究的前沿课题之一。这一问题的研究起源于国际数学大师Erdos等人在七十年代对Ramsey理论的推广，Erdos有多篇文章做这方面的研究，从事过这方面研究的其他著名学者有Alon、Thomassen、Tuza等。本项目旨在将经典图论的方法和概率方法相结合，力争给出一般图中在一些边染色条件（如色度条件，正常染色条件）下异色长圈和异色长路的长度的最优下界；研究路、圈、树等常见子图的anti-Ramsey数或local anti-Ramsey数，确定更多图类的anti-Ramsey数和local anti-Ramsey数；从算法的角度来考虑异色子图问题，通过对边染色图的结构和异色子图（包括异色匹配、异色圈、异色生成树等）存在性的研究，给出其相应的有效算法。这方面的研究已经吸引了许多研究者的关注和兴趣，并将引起更大的研究热潮。

边染色图中的特殊着色子图问题起源于Ramsey 理论，是当代图论研究的前沿课题之一。本项目对边染色图中的单色子图和异色子图问题进行了深入系统的研究，在几个关键性问题上取得了实质性进展。（1）研究边染色图中的异色长路，分别得到了不含异色三角形的边染色，正常边染色，及一般边染色中异色长路路长的下界，一部分结果已经发表在Utilitas上，另一部分结果已经完成投稿。（2）研究边染色图中的异色匹配，对于所有的图G，得到了关于匹配的Constrained-Ramsey数，相关结果已完成并投稿。（3）研究边染色图中的单色高连通子图，基本确定了2-边染色完全多部图中的最大2-连通单色子图的大小，结果已被应用数学学报（英文版）接收。.（4）研究距离2标号染色及距离2标号染色，得到了关于一些图类的距离2标号下的实值边跨度，以及关于一些图类的边的距离2标号染色的上下界及关于放松的距离2标号染色的一系列结果，这些结果一部分已经发表在东南大学学报（英文版）上，另外有些已完成投稿。以上研究结果推动了相关染色问题的研究，具有重要的理论意义。