平面图的点面全染色

设G(V,E,F)为一个平面图.使得集合r(G)∪F(G)中相邻或相关联的元素均染为不同颜色的最少颜色数称为平面图G的点面全色数,记为Xs(G).1968年,G·Ringel提出猜想:对每一个平面图G有Xs(G)≤6. 本文对树、圈、轮形图、扇形图、梯形图和平面格子图等特殊图证实了这个猜想为真.