三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.     

环面图上的一个Lebesgue型定理及其在线性染色中的应用

设c是图G的一个顶点染色, 如果c的任意两个色类都导出一个最大度至多为2的无圈子图,则称c为G的一个无圈染色. 我们首先证明了环面图上的一个Lebesgue 型定理, 作为其应用证明了对任一个围长不小于5 的环面图G, 除非△(G) = 4 而且G有一个子图H使得H的每一个面都是与三个3度点和二个4度点相关的5度面, H一定是(「(△(G))/2」+ 4)- 线性列表可染色的. 这一结果推广和改进了一些已知结论.