看到:
用于五幅平面图的两种线性时间算法David Matula,Yossi Shiloach,Robert Tarjan
(只是谷歌这个,你会发现该论文的PDF).
因此,这是一篇关于在O(n)时间内对平面图进行5色着色的论文,但它首先对6色着色算法进行了简单描述.这是重要的摘录(格式化道歉,这只是一个PDF scrape):
算法6颜色.给定邻接列表形式的n顶点平面图G,该算法确定G的6着色.步骤1. [建立度列表.]对于每个j,其中0-j-n-1,形成双重<<链表j的所有顶点的j. - 步骤2. [标签顶点最小程度最后.]对于i = n,n - 1,n* - 1,...,1将最小j的非空j度列表的第一个顶点指定为顶点t/i.从j度列表中删除vi.对于与G中的tli相邻并且保持在某种程度列表中的每个顶点U',例如f,从jr度列表中删除u'并将u'插入j9-1度列表中.第3步.[颜色顶点.]对于i = 1,2,...,n,指定顶点t)i最小的颜色值(必须是1到6之间的某个整数)不会出现在已经着色的t)i附近的顶点上.