本文選題：非正常染色 + 1-平面圖�。� 參考：《山東師范大學(xué)》2017年碩士論文

【摘要】：本文僅考慮有限,簡(jiǎn)單的無(wú)向圖.設(shè)d1,…,dk是k個(gè)非負(fù)整數(shù).圖G = (V,E)稱為是非正常(d1,…,dk)-可染的,或(d1,…,dk)-可染的,當(dāng)且僅當(dāng)G的點(diǎn)集可以被剖分成V1,…,Vk,使得每個(gè)V1的點(diǎn)導(dǎo)出子圖G[Vi]中點(diǎn)的最大度至多為di,1≤i≤k.當(dāng)d1=…=dk=0時(shí),即為正常k-染色.一個(gè)圖G稱為是1-平面圖的,如果它可以被畫(huà)在平面上使得每條邊至多交叉另外一條邊.1-平面圖的概念由Ringel提出,并猜想每個(gè)1-平面圖都是6-可染的,這已被Borodin(1986.)證明.因?yàn)榇嬖谝粋�(gè)7-正則的1-平面圖,所以界6是緊的.在2005年,任意的一個(gè)1-平面圖是否是(0,0,0,0)-可染的被證明是NP-完備的.作為圖的正常點(diǎn)染色的一種推廣,非正常點(diǎn)染色問(wèn)題已經(jīng)被廣泛研究.1976年,Steinberg提出猜想:每個(gè)不含4-圈和5-圈的平面圖是(0,0,0)-可染的.在這一猜想的推動(dòng)下,得到了許多著名結(jié)果,例如,每個(gè)不含4-圈和5-圈的平面圖是(2,1,0)-和(4,0,0)-可染的等.本文將平面圖的非正常染色推廣到1-平面圖中,在平面圖的非正常染色問(wèn)題的啟發(fā)下,我們主要討論不含長(zhǎng)度為3, 4, 5和6的圈的1-平面圖,即圍長(zhǎng)至少是7的1-平面圖的非正常點(diǎn)染色問(wèn)題.第一章介紹了本論文所涉及的有關(guān)定義,并對(duì)平面圖的非正常染色和1-平面圖的染色的研究現(xiàn)狀做了綜述.在第二章和第三章中,我們假設(shè)1-平面圖G已經(jīng)被嵌入到一個(gè)平面上使得它的每條邊至多交叉另外一條邊,通過(guò)將G中邊的交叉轉(zhuǎn)化成新的4-點(diǎn),得到其關(guān)聯(lián)平面圖G*,并且稱G*中新的4-點(diǎn)為交叉點(diǎn).根據(jù)1-平面圖G及其關(guān)聯(lián)平面圖G*的結(jié)構(gòu)性質(zhì),我們利用權(quán)轉(zhuǎn)移的方法分別證明了圍長(zhǎng)至少是7的1-平面圖是(1,1,1,0)-和(2,0,0,0)-可染的.
[Abstract]:In this paper, only finite, simple undirected graphs are considered. Set up D1,... D k is k nonnegative integers. Fig. G = Vt. E) is called abnormal D 1,... DKG-dyed, or D1,... If and only if the set of points of G can be subdivided into V1,... Such that the maximum degree of the midpoint of every vertex derived subgraph G [Vi] of each V1 is more than 1 鈮，

本文編號(hào)：1792943