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

发布时间：2020-10-28 15:42

　　 本文主要研究了两种特殊图类的染色问题:不含三角形的平面图的列表染色,交叉数为1的图的在线列表染色.不含三角形的平面图的染色问题吸引了很多学者的注意.Grotzsch的一个经典结果即每个不含三角形的平面图是3-可染的.Voigt构造了一个不是3-可选的不含三角形的平面图.Kratochvil和Tuza观察到每一个不含三角形的平面图是4-可选的.我们讨论如下的问题:G是一个不含三角形的平面图,X是G的顶点集的一个子集.L是G的一个列表配置,X中顶点的表长是3,其他顶点的表长是4.X满足什么条件时,G一定是L-可选的.由Kratochvil和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)-VT)中的点v满足f(v)=5,那么G-E(T)是在线f-可选的.
【学位单位】：浙江师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【部分图文】：

图２．１：?ｆ．Ｚ／）没有坏４－圈??
【相似文献】

相关期刊论文 前10条

1 李晓军;曹世鹏;;两类树的独立集多项式的单峰性[J];高等数学研究;2010年04期

2 谢力同;论简单图所含k阶i爪独立集个数的可重构性[J];数学物理学报;2001年02期

3 张莲珠;两类四角系统的匹配数与点独立集数[J];数学研究;1999年03期

4 李国君，刘振宏;3－连通正则无爪图的Hamilton圈[J];数学进展;1996年01期

5 林育青;关于简单图的独立集多项式[J];东北重型机械学院学报;1997年02期

6 高太平,李素珍;关于3-连通非Hamilton无爪图的一个注记[J];山西大学学报(自然科学版);1997年01期

7 程为麟;张忠辅;;关于Ramsey数的若干问题[J];甘肃教育学院学报(自然科学版);1988年01期

8 陈莉;周贺;何海霞;孙宏慧;陆星家;;基于最大权重独立集的行人检测研究[J];宁波工程学院学报;2013年03期

9 梁作松;管梅;单而芳;;块图中的团横贯集和团独立集[J];通化师范学院学报;2010年04期

10 艾尔肯·吾买尔;关于几类Menger型图[J];新疆大学学报(自然科学版);1995年04期

相关博士学位论文 前10条

1 张海良;关于图的两类多项式及相关指数的研究[D];华东师范大学;2013年

2 曹月芬;多角链关于拓扑指标的一些极值问题[D];厦门大学;2008年

3 宋文兔;网络分解在网络编码中的应用[D];北京大学;2012年

4 王世英;图的匹配的若干结构性问题[D];郑州大学;2000年

5 许成鑫;LDPC码度分布特性及扩展性应用研究[D];北京邮电大学;2011年

6 汪定国;正则图的独立集与团横贯[D];上海大学;2013年

7 章舜哲;图的哈密尔顿连通性及支撑树特征研究[D];华中师范大学;2015年

8 张一炜;源于几类信息科学问题的极值组合构型[D];浙江大学;2016年

9 梁作松;图的团横贯与团染色[D];上海大学;2013年

10 杨帆;群连通、圈覆盖及相关问题的研究[D];华中师范大学;2011年

相关硕士学位论文 前10条

1 李晨莹;圈图在张量积下的独立集结构[D];浙江师范大学;2018年

2 胡建章;特殊图类的列表染色和在线列表染色[D];浙江师范大学;2018年

3 王明昕;蜂窝网络中密集D2D通信的资源分配方法研究[D];北京邮电大学;2018年

4 胡幸威;动力系统中有限IP-独立集与其相关问题的研究[D];中国科学技术大学;2017年

5 王华平;点独立集度和的几个结果[D];江西师范大学;2002年

6 向慧芬;模糊独立集系统及模糊拟阵的结构研究[D];重庆大学;2004年

7 邹玲平;格子系统的独立集的计数[D];厦门大学;2007年

8 王吉松;基于最大权重独立集的特征选择方法研究[D];东北师范大学;2013年

9 纪乃丹;图的独立集多项式和Clar覆盖多项式的转移矩阵计算[D];兰州大学;2006年

10 李树花;关于κ-匹配和κ-独立集的极值多联苯链及一些和图的点PI指标[D];新疆师范大学;2010年

本文编号：2860283