關(guān)于一些圖的定向染色.pdf

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