平面图各种构形的4—着色方法

雷明85639720

平面图各种构形的4—着色方法
雷  明
（二〇二三年四月十六曰）

    1，只剩一个顶点未着色的平面图就是平面图的构形。图中任何一个顶点都可以作这个未着色的待着色顶点。
    2，当围栏顶点数小于4（当然围栏顶点占用的颜色数也一定是小于4的），或者尽管围栏顶点数大于等于4，但围栏顶点所占的颜色数仍小于4时，这种构形可直接给待着色顶点着上四种颜色之一，是好着色构形。
    3，除以上2中的好着色构形外，其他的围栏顶点大于等于4的构形，只要围栏顶点占用的颜色数等于4，都是难着色构形。
    4，难着色构形并不是不可4—着色的构形，而是可以通过各种办法转化成好着色构形的。
    5，围栏顶点数大于等于4而占用颜色数等于4的难着色构形，是可以通过待着色顶点的移动，把待着色顶点移动到度是小于等于5的不可避免顶点上。
    6，待着色顶点移动到度是小于4的顶点上，或者度是4或5的顶点上，但围栏顶点占用的颜色数小于4时的构形仍是好着色构形。
    7，待着色顶点移动到度是4的顶点上，或者度是5的顶点上，但围栏顶点占用的颜色数是4的构形，仍是难着色构形。根据其中所含链的不同，解决的办法也就不同。
    8，4度难着色构形1879年坎泊已用坎泊链法证明了这种构形一定都是可4—着色的。
    9，5度难着色构形当不含双环交叉链时，叫K—构形。坎泊也证明了这种构形都是可4—着色的。并且至少可以从围栏顶点中直接空出一种颜色给待着色顶点。
    10，5度难着色构形含有双环交叉链时，叫H—构形。这种构形中也有可以从围栏顶点中直接空出两个同色的情况，也具有K—构形的性质。
    11，不能直接从围栏顶点中空出任何颜色的H—构形才是真正的H一构形。
    12，真正的H—构形中，有经过了关键顶点的环形链的构形，可以用断链交换法使H—构形转化为K—构形，再进行4—着色。
    13，无环形链的真正的H—构形可以通过一个方向的转型法，使H一构形转化为有环形链的并且能连续的移去两个同色的有双环交叉链的H—构形。可以用坎泊链法连续的移去两个同色，也可使用断链交换法。
    14，这种无环形链的真正的H—构形，也可以通过另一个方向的连续转型法，使H—构形转化为仍是无环形链的并且能连续的移去两个同色的有双环交叉链的H—构形。只可以用坎泊链法连续的移去两个同色。
     15，现在，平面图的各种构形都是可4—着色的了，四色猜测也就是正确的了。


雷  明
二〇二三年四月十六曰于长安