本文選題：線性蔭度 + 線性k-蔭度　； 參考：《東南大學(xué)》2015年博士論文

【摘要】：圖G的正常k-全染色是指用k種顏色給V(G)∪ E(G)中的元素進(jìn)行染色,使得任意兩個相鄰的或相關(guān)聯(lián)的元素均染不同的顏色。使得圖G有正常的k-全染色的最小正整數(shù)k稱為G的全色數(shù),記為χ"(G)。類似的,我們可以定義圖G的正常點染色和正常邊染色,對應(yīng)的色數(shù)分別稱為點色數(shù)和邊色數(shù),分別記為χ(G)與χ'(G)。蔭度的概念可以看作是圖的一種染色(不一定是正常的),其中每個色類的導(dǎo)出子圖是一個森林。本文研究了幾種不同的蔭度概念：圖的線性蔭度、線性k-蔭度、k-星蔭度、全蔭度、列表全蔭度和強(qiáng)均勻點蔭度。主要內(nèi)容概括如下：(1)圖的線性蔭度。一個線性森林是指每個連通分支都是路的森林。圖G的線性蔭度是指使得G可以分解成m個線性森林的最小正整數(shù)m,用la(G)表示。本文確定了完全圖與路、完全圖與圈,以及兩個完全圖的笛卡爾積圖的線性蔭度。(2)圖的線性k-蔭度。一個線性k-森林是指每個連通分支都是長度不超過k的路的森林。圖G的線性k-蔭度是指使得G可以分解成m個線性k-森林的最小正整數(shù)m,用lak(G)表示。本文首先研究了兩個圈的笛卡爾積圖的線性2-蔭度,得到了確切的數(shù)值。此外,本文研究了幾類特殊的平面圖,分別給出了這些平面圖的線性2-蔭度的上界。(3)圖的k-星蔭度。一個星是指至多一個頂點的度大于1的樹。一個k-星森林是指所有分支都是頂點數(shù)不超過k+1的星的森林。使得圖G可以分解成m個k-星森林的最小正整數(shù)m,稱為圖G的k-星蔭度,用sak(G)表示。本文討論了最大度不超過3的圖和樹的k-星蔭度的上下界,并給出了兩個相關(guān)的算法。(4)圖的全蔭度和列表全蔭度。在圖G的一個k-全染色f(不一定是正常的)中,若每個色類的元素在全圖中的導(dǎo)出子圖是一個森林,則稱f是圖G的一個無圈k-全染色。使得圖G有一個無圈k-全染色的最小正整數(shù)k稱為圖G的全蔭度,記為ρ"(G)。對于圖G的每個元素x,如果我們都給它指定一個顏色集合L(x),那么我們稱L為G的一個列表。設(shè)L是G的一個給定的列表,如果存在G的一個無圈全染色f,滿足對任意的元素x ∈ V(G) ∪ E(G)都有f(x)∈L(x),則稱f是G的一個無圈列表全染色。若對于滿是|L(x)|≥k的任意可能的列表L,G都有一個無圈列表全染色,則稱G是無圈k-全可選的。使得圖G是無圈k-全可選的最小正整數(shù)k稱為圖G的列表全蔭度,記為ρl"(G)。這兩個概念是Hetherington提出的。此外,他還提出了關(guān)于全蔭度的猜想：對任何簡單圖G,均有本文完全確定了完全圖Kn和完全二部圖Kn,n的全蔭度,證明以上猜想對這兩類圖是成立的。對于Halin圖,我們給出了其列表全蔭度的上界。本文還研究了平面圖的全蔭度,證明了對于△(G)≥13的平面圖和△(G)≥7且不含4-圈的平面圖,全蔭度猜想都是成立的。(5)圖的強(qiáng)均勻點蔭度。設(shè)f是圖G的頂點的一個t-染色,若每個色類的導(dǎo)出子圖的每個分支都是最大度不超過k的樹,則稱f為圖G的一個(t,k)-樹染色。設(shè)f為圖G的一個(t,k)-樹染色且任何兩種不同顏色所染的頂點數(shù)最多相差1,則稱f為圖G的一個均勻(t,k)-樹染色。使得對所有的t'≥t,圖G都具有均勻(t',k)-樹染色的最小正整數(shù)t,稱作強(qiáng)均勻點k-蔭度,記作vak≡(G)。吳建良等人首先提出了這個概念,并且猜想：對任何平面圖G,均有va∞≡(G)=O(1)。在本文中,我們首先研究了完全二部圖Kn,n的強(qiáng)均勻點1-蔭度,得到了一些相關(guān)的結(jié)果。其次,我們研究了兩類特殊的平面圖,分別得到了強(qiáng)均勻點∞-蔭度的上界,從而證明了吳建良的猜想對這兩類平面圖是成立的。
[Abstract]:In this paper , we study several different shade concepts : the linear shade , the linear k - shade , k - star shade , the shade , the total shade of the list and the shade of the strong uniform . Let G be a given list of G . Let G be a given list of G . If we all assign a color set L ( x ) to any possible list L , G of graph G , we call that G is a non - circle k - total coloring . If there is a non - circle full dyeing f of G , it is called G . If there is a non - circle full dyeing f of G , we call f to be one ( t , k ) - tree dyeing of G . Let f be a graph G ( t , k ) - tree dyeing . Let f be a uniform ( t , k ) - tree dyeing of G . If f is a graph G , we call f a uniform ( t , k ) - tree dyeing . The minimum positive integer , t , called strong uniform point k - shade , called strong uniform point k - shade , is known as vak ident ( G ) .
【學(xué)位授予單位】：東南大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O157.5

【相似文獻(xiàn)】

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

1 吳建良;Halin圖的一些路分解[J];山東礦業(yè)學(xué)院學(xué)報;1998年01期

2 楊愛民;線圖的蔭度[J];山西大學(xué)學(xué)報(自然科學(xué)版);1998年01期

3 魏二玲,劉彥佩,楊愛民,康利;乘積圖的蔭度[J];北方交通大學(xué)學(xué)報;2000年02期

4 薛妮妮;嚴(yán)志丹;;關(guān)于曲面的列表點蔭度定義與探討[J];塔里木大學(xué)學(xué)報;2010年01期

5 王雪梅;李會序;;某些不含5-圈的圖的線性2-蔭度[J];科技信息;2011年29期

6 張忠輔;王建方;;蔭度與團(tuán)覆蓋數(shù)的關(guān)系[J];蘭州鐵道學(xué)院學(xué)報;1991年01期

7 張忠輔;王建方;;關(guān)于圖的點蔭度[J];應(yīng)用數(shù)學(xué);1991年02期

8 張建州;;圖的點星蔭度[J];電子科技大學(xué)學(xué)報;1992年01期

9 熊黎明,文莉莉;圖的點線蔭度(英文)[J];江西師范大學(xué)學(xué)報(自然科學(xué)版);1994年02期

10 黃荷姣,魏暹蓀,張江濤;有限圖的邊蔭度分解[J];陜西師范大學(xué)學(xué)報(自然科學(xué)版);1998年04期

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

1 陶f 昀;關(guān)于圖的一些蔭度問題的研究[D];東南大學(xué);2015年

2 左連翠;圖的點蔭度和點線性蔭度[D];山東大學(xué);2005年

3 楊愛峰;圖的廣義著色[D];鄭州大學(xué);2004年

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

1 金政國;平方圖的點蔭度[D];北京交通大學(xué);2010年

2 姚梅;圈限制條件下平面圖的線性2-蔭度[D];河北工業(yè)大學(xué);2015年

3 趙宗正;短圈不相交的平面圖的線性2-蔭度[D];河北工業(yè)大學(xué);2015年

4 郭志偉;圖的強(qiáng)平衡頂點蔭度若干問題研究[D];青海師范大學(xué);2016年

5 黃莉;圖的列表點蔭度[D];浙江師范大學(xué);2016年

6 薛妮妮;圖的列表點蔭度[D];新疆大學(xué);2008年

7 石淼;k-退化圖的M圖的點蔭度[D];北京交通大學(xué);2010年

8 王苒群;幾類圖的線性k-蔭度[D];天津師范大學(xué);2013年

9 馬剛;平方圖的點蔭度[D];山東大學(xué);2007年

10 陶金穎;不含弦5-圈和弦6-圈的平面圖的線性2-蔭度[D];河北工業(yè)大學(xué);2014年

，

本文編號：1966760