圖的在線列表染色是圖的列表染色的在線版本.在線列表染色概念是由Schauz[23]和Zhu[31]于2009年分別提出的.設(shè)G是一個圖,f是一個從V(G)到N的映射.圖G上的f-painting博弈(也稱作在線列表染色游戲)有兩位玩家:Lister和Painter.起初,每一個頂點v有f(v)個籌碼且每個頂點均未被染色.在每個回合,Lister選擇圖中未染色頂點集的一個非空子集M,將M中每個頂點減少一個籌碼.Painter選擇M中一個獨立集I,將I中的頂點染色.如果某個回合結(jié)束后,存在一個頂點未被染色且沒有籌碼了,則Lister贏得比賽.否則,在某一回合,所有頂點均被染色,則Painter贏得比賽.如果Painter在圖G上的f-列表染色游戲中有一個贏的策略,我們說圖G是f-可涂的(也稱作在線f-可選的).如果圖G是f-可涂的且f =k,則稱圖G是k-可涂的.圖G的可涂數(shù)(也叫在線選擇數(shù))用χP(G)表示,是指最小的正整數(shù)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的問題,人們希望確定最小的整數(shù)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-可選的.除了不含固定長度圈的問題,學(xué)者們對限定三角形距離的平面圖的列表染色問題進行了廣泛研究.我們用g表示不含4-,5-,6-圈且三角形距離≥2的平面圖的全體.假設(shè)G∈g,則一個7-面至多和兩個3-面相鄰.假設(shè)f是G的一個7-面,與兩個(3,3,3)的3-面相鄰,f的頂點均為4--點.如果f恰有一個4-點,則稱f為窮面.若f有兩個4-點,則稱f為半窮面.若一個窮面f與一個半窮面g相交于一個4-點或相鄰于一條(3,4)-邊,則稱fUg為G的一個特殊結(jié)構(gòu).Jin和Wei[13]證明了如果平面圖G∈g,不含如圖1.1所示的特殊7-圈,那么G是3-可選的.本文改進了上述結(jié)果.結(jié)合Alon-Tarsi定理和權(quán)轉(zhuǎn)移方法,在第二章中證明了如果平面圖G∈g,不含特殊結(jié)構(gòu),那么G是3-可涂的.在第三章中證明當k=3,4,5或6時,不含k-圈的平面圖是4-可涂的.
【學(xué)位單位】：浙江師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2018
【中圖分類】：O157.5
【部分圖文】：

?（ｂ）?—個半窮面?（ｃ）?一個弱面??圖２．１：定義２．１的圖??定義２．２．設(shè)／：是一個窮面，／２是一個半窮面．如果力和八相交于一個４－點或相鄰于一??條（３，４）－邊，則稱／山／２為Ｇ的一個特殊結(jié)構(gòu)．??

三角形［外巧叫］相鄰．且ｇ的其他頂點的度數(shù)均為３．設(shè)Ｘ?＝?｛…，．．．，叫丨，我們將證??明Ｇ［Ｘ］有一個強的定向，因此Ｇ［Ｘ］是一個可約結(jié)構(gòu)．這與引理２．１矛盾．??因為圖（？不含４－，５－．６－圈且尸》２．所以（？［義］如圖２．３（？）所示．特別的，當；＝??３，４，?５，６，?７，８時，每一個頂點巧有兩個鄰點在久中，有一個鄰點在中．??設(shè)Ｄ?〃是圖Ｇｐｑ的定向，如圖２．３（ｂ）所示．我們將展示是圖Ｇｐｑ的一個強的??定向．顯然對于每一個頂點ｔ，ｅ?Ａ＇．有ｃ＾〃（ｔ；）?＜?２－（ｄＧ（ｔ；）?－ｒｆＧｐ＾（ｔ〇）．為得到ｄｉｆｆ（Ｄ〃）矣??０，由引理２．２可知，我們可以刪去三角形仰］．由觀察２．１可知，在剩下的圖中刪去??源和匯，最終得到的定向圖是一個空圖￡＞〃＇且ｄｉｆｆ（Ｄ＇〃）＝?１．因此ｄｉｆｆ（Ｄ〃）＝?１．?□??１＇８?坤??Ｖ?ｒｅ?ｖ．ｉ／?＼Ｖ（ｉ?ＶｙＴ??（ａ）可能結(jié)構(gòu)?（ｂ）定向圖??圖２．３：引理２．３的圖??定義２．４．如果面／＝［巧巧．．．巧］是一個７－面，與兩個（３，３，３）－三角形７＼?＝［列￥８］和乃＝??［％哪９］相鄰，且／上每一個頂點的度數(shù)至多為４，那么由集合Ｘ??導(dǎo)的子圖ＧｔＸ；ｊ稱為一個企鵝．??引理２．４．圖Ｇ不包含兩個企鶴．其中兩個企鶴相交于一個４－點

?我們構(gòu)造圖的－？個強的定向Ｌ＞＂，如下：首先兩個７－面＆，仍上的邊以及兩??個（３，３，３）－三角形（與汛．仍相鄰的）上的邊的定向如圖２．４（ｄ），２．４（ｅ）和２．４（ｆ）所示．如果??圖Ｇｐｑ上有一條額外邊，則額外邊的定向是任意的．??很容易看出，對于每一個頂點ｒ?ｅ入，有＜?２?－?－如丨應(yīng)用觀??察２．１可使Ｄ?〃成為一個空圖．因此ｄｉｆｆｐ＂）?＝?１．??，八?Ａ?ＡｒＡ??．７１?Ｉ＇ｌｌｆ?．７２?＼?入?■＇?Ｕ７ｆ??Ｉ．丨，，?ｍｕ，＂：?？?？＇??＾７?Ｖ－＇?Ｖ?＼／??（ａ）情況１?（ｂ）情況２??／Ａ＇?＼?＃?＼?ｉ，�。�??，，ｃ?＾?＜?ｉ?Ｖ、
【相似文獻】

相關(guān)碩士學(xué)位論文 前1條

1 顏慧慧;平面圖的在線列表染色[D];浙江師范大學(xué);2018年

本文編號：2894264