边染色图的单色子图和杂色子图划分问题

边染色图的单色子图或杂色子图划分问题，就是用顶点不相交的某种单色子图或杂色子图去划分给定图的顶点集合。Erdos、Gyarfas等于上世纪八、九十年代对此开展了一系列的研究。该问题与Ramsey理论有着十分密切的联系，在图论学科的研究中具有重要的理论意义，这方面问题及其相关的单色（杂色）子图问题引起了多位国际著名学者的研究兴趣，包括Alon，Reed，Thomassen，Tuza等。迄今该问题的研究进展仍比较缓慢，具有较大的难度。本项目拟研究一般图类中某种单色子图和杂色子图的划分问题；从算法的角度研究边染色图的单色子图和杂色子图划分所相关的组合优化问题，确定其算法复杂性，对某些问题设计出有效算法或近似算法；研究边染色图中单色子图和杂色子图划分问题的各种推广情形。这方面的研究吸引着越来越多研究者的关注和兴趣，将成为图论学科中的热点问题之一。