边着色图的单色和异色子图及顶点集合划分问题

边着色图的单色和异色子图（圈、路、树、匹配等）的研究，以及用最少的某种单色或异色子图去划分该图的顶点集合的研究起源于匈牙利学派，国际数学大师Erdos在九十年代前后有多篇文章做这方面的研究，从事过这方面研究的其他重要人物有Alon、Gyarfas、Haxell、Reed、Thomassen、Tuza等，这方面的研究还与Ramsey理论有密切的联系，因此我们选择的研究课题在图论学科中具有重要的理论意义。从已发表的文章来看，这方面的研究难度比较大，研究进展也比较缓慢。本项目拟解决在色度数及色领域并的条件下最长异色路的最佳下界、异色圈问题。研究最大或完美异色匹配问题。用概率方法研究随机边着色下的各种单色和异色子图的存在概率问题。研究顶点集合的某种单色或异色子图的最佳划分问题，研究最佳划分的算法复杂性、多项式时间算法、近似算法等组合优化问题。这些研究将成为图论学科中新的热点问题。