图着色问题

图着色问题（Graph Coloring Problem， GCP） 又称着色问题，是最著名的NP-完全问题之一。道路着色问题（Road Coloring Problem）是图论中最著名的猜想之一。数学定义：给定一个无向图G=（V， E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。图的m-着色判定问题——给定无向连通图G和m种不同的颜色。