图着色问题
维基百科，自由的百科全书
 |
此條目或章节需要擴充，请協助改善这篇條目。（2010年11月30日） 更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 |
 |
此条目没有列出任何参考或来源。（2010年11月30日） 維基百科所有的內容都應該可供查證。 请协助添加来自可靠来源的引用以改善这篇条目。无法查证的内容可能被提出异议而移除。 |
图着色问题（Graph Coloring Problem, GCP），又称着色问题，是最著名的NP-完全问题之一。
给定一个无向图G＝（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。
