【摘要】：圖的染色與標(biāo)號(hào)問(wèn)題是圖論中的重要分支,其研究歷史久遠(yuǎn).作為圖論發(fā)展的先導(dǎo)之一:四色定理,就是典型的染色問(wèn)題.一直以來(lái),圖的染色與標(biāo)號(hào)問(wèn)題備受關(guān)注,它們不僅在圖論上扮演重要角色,而且在社會(huì)科學(xué)、生命科學(xué)等方面都有著廣泛應(yīng)用.圖的染色與標(biāo)號(hào)本質(zhì)上都是從圖的點(diǎn)集或邊集到實(shí)數(shù)集的映射.我們首先研究的是平面圖的鄰點(diǎn)可區(qū)別全染色問(wèn)題.圖G的k-全染色是指用集合[k]中的顏色(即元素)對(duì)圖的點(diǎn)和邊同時(shí)進(jìn)行染色,使得相鄰的點(diǎn)、相鄰的邊以及相關(guān)聯(lián)的點(diǎn)和邊都染不同顏色.對(duì)于G的一個(gè)k-全染色φ,我們用C(v)來(lái)表示由點(diǎn)v以及v的所有關(guān)聯(lián)邊的顏色構(gòu)成的集合.我們稱(chēng)點(diǎn)v和點(diǎn)u是沖突的,如果兩點(diǎn)相鄰且Cφ(v)=Cφ(u).如果G中任意兩個(gè)鄰點(diǎn)都不沖突,則稱(chēng)k-全染色φ是鄰點(diǎn)可區(qū)別的.我們將能夠使得G具有鄰點(diǎn)可區(qū)別全染色的最小的顏色數(shù)k稱(chēng)為圖G的鄰點(diǎn)可區(qū)別全色數(shù),記作χ"a(G).2005年,Zhang等人首次提出這種染色并猜想:對(duì)于至少有兩個(gè)點(diǎn)的連通圖G,均有χ"a(G)≤△(G)+ 3.Cheng等人已經(jīng)證明對(duì)于最大度至少為10的平面圖,上述猜想成立.本文在第二章中證明了對(duì)于最大度△(G)≥9的平面圖G,有χ"a(G)≤ △(G)+ 3,改進(jìn)了已有的結(jié)果,從而推動(dòng)猜想的解決.進(jìn)一步,對(duì)于最大度△(G)≥ 10的平面圖G,我們得到了更好的上界,即χ"a(G)≤ △(G)+ 2.在第三章中,我們主要考慮圖的局部k-反魔幻定向.設(shè)D是圖G的一個(gè)定向且G的邊數(shù)為m,D的局部k-反魔幻標(biāo)號(hào)是指這樣一個(gè)映射:將D的邊集映射到[m + k],使得任意兩條邊的標(biāo)號(hào)(即像)不同,且任意兩個(gè)鄰點(diǎn)的點(diǎn)和互異,其中點(diǎn)和是指該點(diǎn)所有入邊的標(biāo)號(hào)之和減去所有出邊的標(biāo)號(hào)之和.如果D有局部k-反魔幻標(biāo)號(hào),那么就稱(chēng)D是圖G的一個(gè)局部k-反魔幻定向.當(dāng)k = 0時(shí),簡(jiǎn)稱(chēng)局部k-反魔幻標(biāo)號(hào)(定向)為局部反魔幻標(biāo)號(hào)(定向).之所以考慮該問(wèn)題,是受著名的反魔幻標(biāo)號(hào)猜想和1-2-3猜想的啟發(fā).反魔幻標(biāo)號(hào)猜想自1990年被提出以來(lái)受到廣泛關(guān)注,但至今仍未完全解決,其難度在于不僅要求任意兩條邊的標(biāo)號(hào)互異,而且任意兩個(gè)點(diǎn)所關(guān)聯(lián)的邊的標(biāo)號(hào)之和也要不同.而1-2-3猜想只要求區(qū)分鄰點(diǎn),受此啟發(fā),我們開(kāi)始研究圖的局部反魔幻標(biāo)號(hào),進(jìn)而推廣到有向圖.Chang等人猜想:每一個(gè)連通圖都存在一個(gè)局部反魔幻定向.本文中,我們證明了每一個(gè)d-退化圖都存在一個(gè)局部(d + 2)-反魔幻定向,并且該結(jié)論對(duì)于列表形式也成立,其中列表中元素均為正實(shí)數(shù).由于平面圖是5-退化的,因此每一個(gè)平面圖都存在一個(gè)局部7-反魔幻定向.
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：O157.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 黃丹君;王維凡;;高度平面圖的鄰點(diǎn)可區(qū)別全染色[J];中國(guó)科學(xué):數(shù)學(xué);2012年02期

本文編號(hào)：2717093