平面图的点着色

将连通无桥 平面图 的平面嵌入和所有的面称为地图. 将地图的面称为国家.

对 $G$ 的每个国家图上一种颜色, 相邻国家涂不同的颜色, 称为地图 $G$ 的面着色.

能用 $k$ 种颜色给 $G$ 的面着色, 称为 $G$ 是 $k$- 面可着色的.

最少用 $k$ 种颜色给 $G$ 的面着色, 称为 $G$ 的面色度 ${\chi }^{\ast }(G)=k$.

定理 地图 $G$ 是 $k$- 面可着色的当且仅当对偶图 $G^{\ast }$ 是 $k-$ 点可着色的.

定理 任何平面图都是 $4-$ 可着色的.