极大平面图的结构与着色理论 (3)纯树着色与唯一4-色极大平面图猜想

Theory on Structure and Coloring of Maximal Planar Graphs (3) Purely Tree-colorable and Uniquely 4-colorable Maximal Planar Graph Conjectures

一个极大平面图若是从K_4出发,不断地在三角面上嵌入3度顶点得到的,则称此极大平面图为递归极大平面图。唯一4-色极大平面图猜想是指:一个平面图是唯一4-可着色的当且仅当它是递归极大平面图。此猜想已有43年历史,是图着色理论中继四色猜想之后另一个著名的未解猜想。为此,该文相继深入研究了哑铃极大平面图与递归极大平面图的结构与特性,结合该系列文章(2)的扩缩运算,给出了证明唯一4-色极大平面图猜想的一种思路。

A maximal planar graph is called the recursive maximal planar graph if it can be obtained from K4 by embedding a 3-degree vertex in some triangular face continuously. The uniquely 4-colorable maximal planar graph conjecture states that a planar graph is uniquely 4-colorable if and only if it is a recursive maximal planar graph. This conjecture, which has 43 years of history, is a very influential conjecture in graph coloring theory after the Four-Color Conjecture. In this paper, the structures and properties of dumbbell maximal planar graphs and recursive maximal planar graphs are studied, and an idea of proving the uniquely 4-eolorable maximal planar graph conjecture is proposed based on the extending-contracting operation proposed in this series of article （2）.