图着色问题

图着色问题（Graph Coloring Problem, GCP）　又称着色问题，是最著名的NP-完全问题之一。

一，路线着色问题

是图论中最著名的猜想之一。通俗的说，这个猜想认为，可以绘制一张“万能地图”，指导人们到达某一目的地，不管他们原来在什么位置。这个猜想最近被以色列数学家Avraham Trahtman在2007年9月证明。

举个例子。在维基网给出的图例中，如果按图中所示方式将16条边着色，那么不管你从哪里出发，按照“蓝红红蓝红红蓝红红”的路线走9步，你最后一定达到黄色顶点。路线着色定理就是说在满足一定条件的有向图中，这样的着色方式一定存在。严格的数学描述如下。我们首先来定义同步着色。G是一个有限有向图并且G的每个顶点的出度都是k。G的一个同步着色满足以下两个条件：1)G的每个顶点有且只有一条出边被染成了1到k之间的某种颜色；2)G的每个顶点都对应一种走法，不管你从哪里出发，按该走法走，最后都结束在该顶点。有向图G存在同步着色的必要条件是G是强连通而且是非周期的。一个有向图是非周期的是指该图中包含的所有环的长度没有大于1的公约数。路线着色定理这两个条件(强连通和是非周期)也是充分的。也就是说,有向图G存在同步着色当且仅当G是强连通而且是非周期的。