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

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

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

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

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

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

本文編號(hào)：2894264