3着色问题 设G=(V,E)是无向图，G的有效着色是指对所有顶点的颜色指派，使得每个顶点被指派一种颜色并且相邻顶点不被指派成相同颜色。 问题：给定无向图G=(V,E)，判定G是否可以被3种颜色着色。 定理11.8：3着色问题是NP完全的。 将3SAT问题归约到3着色问题