着色图中具有给定性质的子图和最优子图问题

本项目研究着色图中具有给定性质的子图的存在性和最优子图问题。研究这种最优子图的寻求算法和复杂性估计，另一方面，对给定具有某种性质的子图，估计所需颜色的最少数目，使得用这些颜色对图任意或某种着色，都存在具有这种性质的子图，例如，边色各异的给定长度的圈或路，支撑树等。为图的理论发展和组合优化与算法的研究开辟了新的研究方向。