平面图的在线列表染色
发布时间：2020-11-22 06:17
图的在线列表染色是图的列表染色的在线版本.在线列表染色概念是由Schauz[23]和Zhu[31]于2009年分别提出的.设G是一个图,f是一个从V(G)到N的映射.图G上的f-painting博弈(也称作在线列表染色游戏)有两位玩家:Lister和Painter.起初,每一个顶点v有f(v)个筹码且每个顶点均未被染色.在每个回合,Lister选择图中未染色顶点集的一个非空子集M,将M中每个顶点减少一个筹码.Painter选择M中一个独立集I,将I中的顶点染色.如果某个回合结束后,存在一个顶点未被染色且没有筹码了,则Lister赢得比赛.否则,在某一回合,所有顶点均被染色,则Painter赢得比赛.如果Painter在图G上的f-列表染色游戏中有一个赢的策略,我们说图G是f-可涂的(也称作在线f-可选的).如果图G是f-可涂的且f =k,则称图G是k-可涂的.图G的可涂数(也叫在线选择数)用χP(G)表示,是指最小的正整数k使得图G是kk-可涂的.Alon-Tarsi定理[1]是研究列表染色的一个强有力的工具,Schauz[23]将Alon-Tarsi定理延拓至在线列表染色的研究上.图的染色的一个研究方向是源自1976年的Steinberg猜想[12].这个猜想断言不含4-圈和5-圈的平面图是3-可染的.Erdos[20]在1991年提出确定最小的k使得不含4-,5-,...,k-圈的平面图是3-可染的.最近,Steinberg的猜想被Cohen-Addad,Hebdige,Kral[5]等人否定.但是不含4-,5-,6-圈的平面图是否3-可染的这一问题,目前尚未解决.类似Erdos的问题,人们希望确定最小的整数l使得不含4-,5-,...,l-圈的平面图是3-可选的.2010年,Borodin等人[2]证明了l ≤ 9.最近Dvorak和Postle[7]证明l ≤ 8.Lam,Xu和Liu[16]证明了不含4-圈的平面图是4-可选的;Wang和Lih[27]证明了不含5-圈的平面图是4-可选的;Juvan和Mohar[14]证明了不含6-圈的平面图是4-可选的.除了不含固定长度圈的问题,学者们对限定三角形距离的平面图的列表染色问题进行了广泛研究.我们用g表示不含4-,5-,6-圈且三角形距离≥2的平面图的全体.假设G∈g,则一个7-面至多和两个3-面相邻.假设f是G的一个7-面,与两个(3,3,3)的3-面相邻,f的顶点均为4--点.如果f恰有一个4-点,则称f为穷面.若f有两个4-点,则称f为半穷面.若一个穷面f与一个半穷面g相交于一个4-点或相邻于一条(3,4)-边,则称fUg为G的一个特殊结构.Jin和Wei[13]证明了如果平面图G∈g,不含如图1.1所示的特殊7-圈,那么G是3-可选的.本文改进了上述结果.结合Alon-Tarsi定理和权转移方法,在第二章中证明了如果平面图G∈g,不含特殊结构,那么G是3-可涂的.在第三章中证明当k=3,4,5或6时,不含k-圈的平面图是4-可涂的.
【学位单位】：浙江师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【部分图文】：
?（ｂ）?—个半穷面?（ｃ）?一个弱面??图２．１：定义２．１的图??定义２．２．设／：是一个穷面，／２是一个半穷面．如果力和八相交于一个４－点或相邻于一??条（３，４）－边，则称／山／２为Ｇ的一个特殊结构．??
三角形［外巧叫］相邻．且ｇ的其他顶点的度数均为３．设Ｘ?＝?｛…，．．．，叫丨，我们将证??明Ｇ［Ｘ］有一个强的定向，因此Ｇ［Ｘ］是一个可约结构．这与引理２．１矛盾．??因为图（？不含４－，５－．６－圈且尸》２．所以（？［义］如图２．３（？）所示．特别的，当；＝??３，４，?５，６，?７，８时，每一个顶点巧有两个邻点在久中，有一个邻点在中．??设Ｄ?〃是图Ｇｐｑ的定向，如图２．３（ｂ）所示．我们将展示是图Ｇｐｑ的一个强的??定向．显然对于每一个顶点ｔ，ｅ?Ａ＇．有ｃ＾〃（ｔ；）?＜?２－（ｄＧ（ｔ；）?－ｒｆＧｐ＾（ｔ〇）．为得到ｄｉｆｆ（Ｄ〃）矣??０，由引理２．２可知，我们可以删去三角形仰］．由观察２．１可知，在剩下的图中删去??源和汇，最终得到的定向图是一个空图￡＞〃＇且ｄｉｆｆ（Ｄ＇〃）＝?１．因此ｄｉｆｆ（Ｄ〃）＝?１．?□??１＇８?坤??Ｖ?ｒｅ?ｖ．ｉ／?＼Ｖ（ｉ?ＶｙＴ??（ａ）可能结构?（ｂ）定向图??图２．３：引理２．３的图??定义２．４．如果面／＝［巧巧．．．巧］是一个７－面，与两个（３，３，３）－三角形７＼?＝［列￥８］和乃＝??［％哪９］相邻，且／上每一个顶点的度数至多为４，那么由集合Ｘ??导的子图ＧｔＸ；ｊ称为一个企鹅．??引理２．４．图Ｇ不包含两个企鹤．其中两个企鹤相交于一个４－点
?我们构造图的－？个强的定向Ｌ＞＂，如下：首先两个７－面＆，仍上的边以及两??个（３，３，３）－三角形（与汛．仍相邻的）上的边的定向如图２．４（ｄ），２．４（ｅ）和２．４（ｆ）所示．如果??图Ｇｐｑ上有一条额外边，则额外边的定向是任意的．??很容易看出，对于每一个顶点ｒ?ｅ入，有＜?２?－?－如丨应用观??察２．１可使Ｄ?〃成为一个空图．因此ｄｉｆｆｐ＂）?＝?１．??，八?Ａ?ＡｒＡ??．７１?Ｉ＇ｌｌｆ?．７２?＼?入?■＇?Ｕ７ｆ??Ｉ．丨，，?ｍｕ，＂：?？?？＇??＾７?Ｖ－＇?Ｖ?＼／??（ａ）情况１?（ｂ）情况２??／Ａ＇?＼?＃?＼?ｉ，！＞??，，ｃ?＾?＜?ｉ?Ｖ、
【相似文献】
本文编号：2894264
【学位单位】：浙江师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【部分图文】：
?（ｂ）?—个半穷面?（ｃ）?一个弱面??图２．１：定义２．１的图??定义２．２．设／：是一个穷面，／２是一个半穷面．如果力和八相交于一个４－点或相邻于一??条（３，４）－边，则称／山／２为Ｇ的一个特殊结构．??
三角形［外巧叫］相邻．且ｇ的其他顶点的度数均为３．设Ｘ?＝?｛…，．．．，叫丨，我们将证??明Ｇ［Ｘ］有一个强的定向，因此Ｇ［Ｘ］是一个可约结构．这与引理２．１矛盾．??因为图（？不含４－，５－．６－圈且尸》２．所以（？［义］如图２．３（？）所示．特别的，当；＝??３，４，?５，６，?７，８时，每一个顶点巧有两个邻点在久中，有一个邻点在中．??设Ｄ?〃是图Ｇｐｑ的定向，如图２．３（ｂ）所示．我们将展示是图Ｇｐｑ的一个强的??定向．显然对于每一个顶点ｔ，ｅ?Ａ＇．有ｃ＾〃（ｔ；）?＜?２－（ｄＧ（ｔ；）?－ｒｆＧｐ＾（ｔ〇）．为得到ｄｉｆｆ（Ｄ〃）矣??０，由引理２．２可知，我们可以删去三角形仰］．由观察２．１可知，在剩下的图中删去??源和汇，最终得到的定向图是一个空图￡＞〃＇且ｄｉｆｆ（Ｄ＇〃）＝?１．因此ｄｉｆｆ（Ｄ〃）＝?１．?□??１＇８?坤??Ｖ?ｒｅ?ｖ．ｉ／?＼Ｖ（ｉ?ＶｙＴ??（ａ）可能结构?（ｂ）定向图??图２．３：引理２．３的图??定义２．４．如果面／＝［巧巧．．．巧］是一个７－面，与两个（３，３，３）－三角形７＼?＝［列￥８］和乃＝??［％哪９］相邻，且／上每一个顶点的度数至多为４，那么由集合Ｘ??导的子图ＧｔＸ；ｊ称为一个企鹅．??引理２．４．图Ｇ不包含两个企鹤．其中两个企鹤相交于一个４－点
?我们构造图的－？个强的定向Ｌ＞＂，如下：首先两个７－面＆，仍上的边以及两??个（３，３，３）－三角形（与汛．仍相邻的）上的边的定向如图２．４（ｄ），２．４（ｅ）和２．４（ｆ）所示．如果??图Ｇｐｑ上有一条额外边，则额外边的定向是任意的．??很容易看出，对于每一个顶点ｒ?ｅ入，有＜?２?－?－如丨应用观??察２．１可使Ｄ?〃成为一个空图．因此ｄｉｆｆｐ＂）?＝?１．??，八?Ａ?ＡｒＡ??．７１?Ｉ＇ｌｌｆ?．７２?＼?入?■＇?Ｕ７ｆ??Ｉ．丨，，?ｍｕ，＂：?？?？＇??＾７?Ｖ－＇?Ｖ?＼／??（ａ）情况１?（ｂ）情况２??／Ａ＇?＼?＃?＼?ｉ，！＞??，，ｃ?＾?＜?ｉ?Ｖ、
【相似文献】
相关硕士学位论文 前1条
1 颜慧慧;平面图的在线列表染色[D];浙江师范大学;2018年
本文编号：2894264
本文链接：https://www.wllwen.com/kejilunwen/yysx/2894264.html
