论文部分内容阅读
本文主要研究了两种特殊图类的染色问题:不含三角形的平面图的列表染色,交叉数为1的图的在线列表染色. 不含三角形的平面图的染色问题吸引了很多学者的注意.Gr(o)tzsch的一个经典结果即每个不含三角形的平面图是3-可染的.Voigt构造了一个不是3-可选的不含三角形的平面图.Kratochvíl和Tuza观察到每一个不含三角形的平面图是4-可选的.我们讨论如下的问题:G是一个不含三角形的平面图,X是G的顶点集的一个子集.L是G的一个列表配置,X中顶点的表长是3,其他顶点的表长是4.X满足什么条件时,G一定是L-可选的.由Kratochvíl和Tuza的结果可知,X是空集时,则G一定是L-可染的.由Voigt的结果可知,对于某些G,存在X,G不是L-可染的.在本文我们证明了一个结果:如果X是G中的一个独立集,那么G是L-可染的.我们进一步猜想:如果G[X]是一个二部图,那么G是L-可染的. 在线列表染色概念是由U.Schauz和X.Zhu于2009年分别提出.在线列表染色概念被提出以来,不少学者研究了各种图类的在线列表染色.U.Schauz证明了平面图是在线5-可选的,M.Han和X.Zhu证明了局部平面图是在线5-可选的,M.Han和X.Zhu证明了每个局部平面图是2-缺陷在线4-可选的,等相关性成果.我们证明了交叉数为1的图是在线5-可选的.在研究过程中我们证明了如下结果:令G是一个交叉数至多为1的图,T=[t1t2t3]为G中的一个三角形,f是V(G)到N的一个映射.如果V(T)中的点v满足f(v)=1,V(G)-V(T)中的点v满足f(v)=5,那么G-E(T)是在线f-可选的.