特殊图类的列表染色和在线列表染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:iris_1204
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要研究了两种特殊图类的染色问题:不含三角形的平面图的列表染色,交叉数为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-可选的.
其他文献
生物资源的可持续发展本质上体现为生物系统的长期持续生存.系统能否持久的条件研究在生物学和经济学方面都有重大意义,近年来受到学术界的高度重视,许多学者对此进行了广泛而
新中国成立以来,中国的航天技术取得了举世瞩目的成绩,中国的航天强国梦一直激励着我们一代又一代的华夏儿女.从中国第一颗人造卫星东方红一号,到后来的第一艘载人航天飞行器神
碳纳米管和Tutte多项式是近年来受到国际上化学和数学研究者们关注的领域。本文主要利用删除—限制方法来计算一类碳纳米管状图的Tutte多项式。   随着碳纳米管状图的横向
巡航制导中的景象匹配是无人飞行器视觉测量的一部分,测量环境比一般地面机器视觉测量复杂性高。文章对巡航制导中的景象匹配算法做了如下研究:首先,建立了巡航制导中景象匹
生存分析是近二三十年来数理统计新分支,它是根据医学,生命科学,可靠性科学,保险科学中的大量实际问题提出的,它可以广义地认为对生存时间(非负随机变量)的一类统计分析技术,主要研
现阶段,我国模具加工技术虽然经过长期发展与完善,但仍存在一些不足之处,例如,切削参数设置、刀具选择以及加工路径选择等。本文简要分析了数控铣加工模具零件工艺,并在此基
延迟积分微分方程(DIDEs)在社会的各个方面是广泛存在的,如经济、生物、物理、工程及航天航空等领域。近年来,延迟积分微分方程的稳定性理论得到了极大的发展,使得延迟积分微分