5—轮构形的可4—着色方法

雷明85639720

5—轮构形的可4—着色方法
雷  明
（二○二一年五月九日）

平面图的不可避免集中的1—轮构形，2—轮构形，3—轮构形都是不会遇到颜色冲突的，其待着色顶点都是可以直接着上四种颜色之一的。而4—轮构形的颜色冲突情况，坎泊早已证明是可约的了。现在就只有5—轮构形一种在发生了颜色冲突时，如何着色的问题需要解决了。这个问题解决了，任何平面图就都是可以4—着色的了。现以ABA型的5—轮（如图1）为例进行分析如下：

5—轮构形分为两大类：一是无双环交叉链A—C和A—D的K—构形，坎泊早已解决，是可约的；一类是有双环交叉链A—C和A—D的H—构形。这一类构形又可分为两类：一类是含有经过了关键顶点的环型链的构形，用断链交换法进行解决；一类是无经过关键顶点的环形链的构形，用转型交换法进行解决。
含有经过了关键顶点的环形链的构形又有两种：一种是有环形链A—B的构形，交换经过了关键顶点的C—D链，构形转化成可约的K—构形，再使用空出颜色的交换法就可解决问题；一种是有环形链C—D的构形，交换经过了关键顶点的A—B链，构形也转化成可约的K—构形，再使用空出颜色的交换法就可解决问题。
不含经过关键顶点的环形链的构形，有两种解决办法：一是对角链交换的转型法，即交换1B—4D的B—D链或交换3B—5C的B—C链，不超过五次即可转化成可约的K—构形，问题就得到解决；一是邻角链交换的转型法，即交换1B—5C的B—C链或交换3B—4D的B—D链，不超过三次即可转化成可约的K—构形，问题也就得到解决。
无双环交叉链的是属于K—构形，有双环交链的构形是属于H—构形。解决H—构形的关键就是破坏其中的双环交叉链。在H—构形中有四个顶点是关键的顶点，如双环交叉链的起点1A，交叉顶点A（图1中未画出来），双环交叉链的两个末端顶点C和D。这四个顶点中只要有任何一个顶点的颜色发生了改变，双环交叉链也就断开了。这就是以上所说的断链交换法和转型交换法。

雷  明
二○二一年五月九日于长安

    注：此文已于二○二一年五月九日在《中国博士网》上发表过，网址是：

雷明85639720

，，，，，，，，