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

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

一种特殊的多米诺扩缩运算

该文提出一种称为334扩缩运算的多米诺扩缩运算。使用该运算构造了一类特殊的极大平面图——334-型极大平面图,证明了该类图均为树型2-色不变圈着色,且每个4k-阶334-型极大平面图恰有2^(k-1)个2-色不变圈着色及2^(k-2)个树着色。证明了该运算可用于构造纯树着色极大平面图,并提出猜想:若极大平面图G是纯树(纯圈,混合)着色,则对G实施334扩(缩)轮运算后,所得之图仍是纯树(纯圈,混合)着色。