

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、一個(gè)定向圖就是指一個(gè)無向圖的定向,即給它的每條邊一個(gè)方向.本文所說的定向圖都是簡單的有向圖,即無環(huán)或無重弧的有向圖.對(duì)一個(gè)定向圖,我們用V(G)、A(G)、δ(G)、Δ(G)分別表示圖G的點(diǎn)集、弧集、最小度和最大度,d(v)表示點(diǎn)v的度.如果u、v是圖G中兩個(gè)相鄰的點(diǎn),用uv表示從u到u的?。瓽的階數(shù)即為圖G的點(diǎn)數(shù).
假設(shè)G和H是兩個(gè)有向圖,那么從G到H的一個(gè)同態(tài)是指一個(gè)作用在V(G)到V(H)的一個(gè)映射Ψ,滿足:(x,y
2、)∈E(G)(→)(Ψ(x),Ψ(y))∈E(H),則稱H是G的一個(gè)目標(biāo)圖,記作G→H.
圖H的一個(gè)k-正常染色是指將圖H的點(diǎn)集分成k個(gè)子集(顏色類)的一個(gè)剖分,且滿足任何兩個(gè)相鄰的點(diǎn)不屬于同一個(gè)子集,相當(dāng)于從H到完全圖Kk的一個(gè)同態(tài),那么圖H的染色教x(H)就可以定義為H的所有k-正常染色中最小的k即k滿足H→Kk,H(?)Kk-1.
一個(gè)定向圖G的一個(gè)k-定向染色是指將點(diǎn)集V(G)分成k個(gè)子集(顏色類)的
3、一個(gè)剖分,且滿足:(1)任何兩個(gè)相鄰的點(diǎn)不屬于同一個(gè)子集;(2)任何兩個(gè)子集之間的弧都有相同的方向,同樣定向圖G的定向色數(shù)xo(H)可以定義為G的所有k-定向染色中最小的k,即k為滿足G→H的所有定向圖H的最小階,也就是G的所有目標(biāo)圖的最小階.對(duì)于一個(gè)無向圖,它的定向色數(shù)是指它的所有定向中的最大的定向色數(shù).其中強(qiáng)定向染色是指目標(biāo)圖為Cayley圖的定向染色,強(qiáng)定向染色數(shù)記為xs(H).
關(guān)于圖的定向染色,Kostochka
4、和Sopena等人做了圖的無圈定向色數(shù)的研究,Robert Samal研究了平面圖的強(qiáng)定向染色,Ochem研究了無三角平面圖的定向染色,Borodin等人研究了給定圍長的全體平面定向圖,并在2004年發(fā)表了圍長不限的稀疏圖之間的同態(tài)問題的文章,同時(shí)對(duì)一個(gè)圖的最大平均度與定向色數(shù)之間的關(guān)系也作了深入研究.
本文主要研究幾類退化圖,雙外平面圖和特殊平面圖的強(qiáng)定向染色問題,得到如下結(jié)果:
定理1令G為2-退化圖,則
5、xs(G)≤7.
定理2令G為3-退化圖,則xs(G)≤19.
定理3令G為4-退化圖,則xs(G)≤67.
定理4令G為雙外平面圖,且G不同構(gòu)于P,則x8(G)≤19,xs(P)≤67.
定理5設(shè)G為平面圖,且G不舍4-7圈,則xs(G)≤19.
對(duì)上述問題本文主要是運(yùn)用可約化的方法和權(quán)值重新分配的方法來證明的.
在本文的最后我們對(duì)定向染色的定義進(jìn)行了
6、推廣,定義了一種新的染色-有向2-路染色.
令m為大于等于1的整數(shù).定向圖G的一個(gè)有向m-路k染色f是指一個(gè)映射f:V(G)→{1,2,…,k},滿足:(1)對(duì)任意的兩個(gè)點(diǎn)x,y,如果1≤(?)(x,y)≤m,則f(x)≠f(y);(2)任何兩個(gè)子集之間的弧都有相同的方向.定向圖G的有向m路色數(shù)xm(G)是指G的所有有向m-路k染色f的最小的k.那么無向圖G的有向m-路色數(shù)xm(G)是它的所有定向圖的有向m-路色數(shù)xm(G
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 關(guān)于圖BBC染色的一些結(jié)果.pdf
- 一些圖的圓邊染色.pdf
- 關(guān)于圖的鄰點(diǎn)可區(qū)別全染色的一些結(jié)果.pdf
- 一些圖的均勻鄰強(qiáng)邊染色.pdf
- 關(guān)于圖的鄰點(diǎn)(強(qiáng))可區(qū)別全染色的一些結(jié)果.pdf
- 關(guān)于一些圖的Ramsey數(shù).pdf
- 關(guān)于正規(guī)圖的一些結(jié)果.pdf
- 關(guān)于一些圖類的虧格問題.pdf
- 關(guān)于多部圖的一些性質(zhì)研究.pdf
- 關(guān)于一些圖類的交叉數(shù).pdf
- 13434.圖的邊染色及一些有限制條件的染色
- 關(guān)于對(duì)稱圖的一些注記.pdf
- 一些圖的點(diǎn)鄰點(diǎn)可區(qū)別全染色.pdf
- 圖的點(diǎn)可區(qū)別邊染色的一些結(jié)果.pdf
- 關(guān)于一些圖的譜刻畫研究.pdf
- 關(guān)于一些圖的譜確定的研究.pdf
- 關(guān)于圖的邊分解的一些結(jié)果.pdf
- 關(guān)于一些圖的譜確定的研究
- 關(guān)于長壽的一些調(diào)查
- 關(guān)于網(wǎng)站的一些想法
評(píng)論
0/150
提交評(píng)論