平面图的4-着色的简单布尔方程表示

A Simple Boolean Representation of 4-Coloring of Planar Graphs

如果一个无环平面图 G至多有一个非三角形的面 ,则称 G为准极大平面图 ( near-trian-gulation) .本文给出了极大平面图和准极大平面图 4 -着色的一类布尔方程表示式 ,该布尔方程所含变元较少 ,结构简单 ,具有良好的递归性质 ,为利用计算机寻找给定平面图的 4 -着色提供了很好的算法 .

This paper provides a simle Boolean representation of proper 4 coloring of near triangulations.The Boolean representation has fewer variables,simpler structure,and better recursive property.It also offers an effective algorithm for finding all proper 4 colorings of any given near triangulation.