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

【摘要】：本文僅考慮有限,簡單的無向圖.設(shè)d1,…,dk是k個非負整數(shù).圖G = (V,E)稱為是非正常(d1,…,dk)-可染的,或(d1,…,dk)-可染的,當且僅當G的點集可以被剖分成V1,…,Vk,使得每個V1的點導(dǎo)出子圖G[Vi]中點的最大度至多為di,1≤i≤k.當d1=…=dk=0時,即為正常k-染色.一個圖G稱為是1-平面圖的,如果它可以被畫在平面上使得每條邊至多交叉另外一條邊.1-平面圖的概念由Ringel提出,并猜想每個1-平面圖都是6-可染的,這已被Borodin(1986.)證明.因為存在一個7-正則的1-平面圖,所以界6是緊的.在2005年,任意的一個1-平面圖是否是(0,0,0,0)-可染的被證明是NP-完備的.作為圖的正常點染色的一種推廣,非正常點染色問題已經(jīng)被廣泛研究.1976年,Steinberg提出猜想:每個不含4-圈和5-圈的平面圖是(0,0,0)-可染的.在這一猜想的推動下,得到了許多著名結(jié)果,例如,每個不含4-圈和5-圈的平面圖是(2,1,0)-和(4,0,0)-可染的等.本文將平面圖的非正常染色推廣到1-平面圖中,在平面圖的非正常染色問題的啟發(fā)下,我們主要討論不含長度為3, 4, 5和6的圈的1-平面圖,即圍長至少是7的1-平面圖的非正常點染色問題.第一章介紹了本論文所涉及的有關(guān)定義,并對平面圖的非正常染色和1-平面圖的染色的研究現(xiàn)狀做了綜述.在第二章和第三章中,我們假設(shè)1-平面圖G已經(jīng)被嵌入到一個平面上使得它的每條邊至多交叉另外一條邊,通過將G中邊的交叉轉(zhuǎn)化成新的4-點,得到其關(guān)聯(lián)平面圖G*,并且稱G*中新的4-點為交叉點.根據(jù)1-平面圖G及其關(guān)聯(lián)平面圖G*的結(jié)構(gòu)性質(zhì),我們利用權(quán)轉(zhuǎn)移的方法分別證明了圍長至少是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 鈮，

本文編號：1792943