关于平面图的完全着色

1 引言图的着色是图论的重要内容之一。据不同实际问题,着色又分点着色、面着色及联合着色或特定着色。不管哪种着色,确定其相应的色数,已被公认为是十分困难的。本文考虑的是具有点集V,边集E和面集F的平面G(V,E,F),不考虑面则记为G(V,E)其中面∫∈F的边和边界上的顶点称为与∫相关联,边e∈E的两端点称为与e相关联。有边连接的两顶点、从同一顶点引出的两边、边界上有公共边的两面,分别叫做相邻的。