摘要： 图的着色问题是一个NP难问题，本文着重探讨无向图的顶点的三色问题，提出了用构造三角环的极大独立集方法判断并尝试给出顶点三色问题的可行解，解决了顶点三色的可满足性问题，克服了以前图遍历过程中的回溯问题，以及由此推论顶点四色和五色问题的极大独立集。

关键词: 顶点着色 三角 极大独立集 题解 可满足性问题 NP难问题 着色问题 三色 无向图 可行解 图遍历