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

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

围长2l+1且无长奇洞图的染色问题

称一个图中长度至少为4的导出圈为该图的洞,长度为奇数和偶数的洞分别被称为奇洞和偶洞.由Petersen图去掉一条2长路的顶点所得到的图记为θ^(-),由Petersen图去掉一对相邻顶点所得到的图记为θ^(+),由θ^(+)去掉一条关联两个3度顶点的边所得到的图记为θ.设l≥2为整数且令r=min{l-1,[l/2]+1},G_(l)表示围长为2l+1且不含其他长度奇洞的图类,G∈G_(l),u∈V(G),S■V(G)是一个非空子集.用G[S]表示由S导出的子图,定义d(u,S)=min{d(u,v):v∈S},并定义Li(S)={u∈V(G)且d(u,S)=i}.本文证明了,如果G[S]连通且对于每一个整数i∈{1,…,r}而言G[Li(S)]都是二部图,则对于所有整数i>0,G[Li(S)]都是二部图,从而χ(G)≤4.本文还证明了,若非Petersen图G∈G_(2)3-连通且所有3-顶点割集都是独立集,则G有导出子图θ或者θ^(-)但没有导出子图θ^(+).作为其推论,若图G∈G_(2)的导出子图中既没有θ又没有θ^(-),则χ(G)≤3,并且G_(2)中极小非3-可染色图一定不包含θ^(+)为导出子图.