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

1、一個定向圖就是指一個無向圖的定向，即給它的每條邊一個方向．本文所說的定向圖都是簡單的有向圖，即無環(huán)或無重弧的有向圖．對一個定向圖，我們用V(G)、A(G)、δ(G)、Δ(G)分別表示圖G的點集、弧集、最小度和最大度，d(v)表示點v的度．如果u、v是圖G中兩個相鄰的點，用uv表示從u到u的弧．G的階數(shù)即為圖G的點數(shù)．
　　 假設(shè)G和H是兩個有向圖，那么從G到H的一個同態(tài)是指一個作用在V(G)到V(H)的一個映射Ψ，滿足：(x，y

2、)∈E(G)（→）(Ψ(x)，Ψ（y））∈E(H)，則稱H是G的一個目標圖，記作G→H.
　　 圖H的一個k-正常染色是指將圖H的點集分成k個子集（顏色類）的一個剖分，且滿足任何兩個相鄰的點不屬于同一個子集，相當(dāng)于從H到完全圖Kk的一個同態(tài)，那么圖H的染色教x(H)就可以定義為H的所有k-正常染色中最小的k即k滿足H→Kk，H（？）Kk-1．
　　 一個定向圖G的一個k-定向染色是指將點集V(G)分成k個子集（顏色類）的

3、一個剖分，且滿足：(1)任何兩個相鄰的點不屬于同一個子集；(2)任何兩個子集之間的弧都有相同的方向，同樣定向圖G的定向色數(shù)xo(H)可以定義為G的所有k-定向染色中最小的k，即k為滿足G→H的所有定向圖H的最小階，也就是G的所有目標圖的最小階.對于一個無向圖，它的定向色數(shù)是指它的所有定向中的最大的定向色數(shù)．其中強定向染色是指目標圖為Cayley圖的定向染色，強定向染色數(shù)記為xs（H）．
　　 關(guān)于圖的定向染色，Kostochka

4、和Sopena等人做了圖的無圈定向色數(shù)的研究，Robert Samal研究了平面圖的強定向染色，Ochem研究了無三角平面圖的定向染色，Borodin等人研究了給定圍長的全體平面定向圖，并在2004年發(fā)表了圍長不限的稀疏圖之間的同態(tài)問題的文章，同時對一個圖的最大平均度與定向色數(shù)之間的關(guān)系也作了深入研究．
　　 本文主要研究幾類退化圖，雙外平面圖和特殊平面圖的強定向染色問題，得到如下結(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．
　　 對上述問題本文主要是運用可約化的方法和權(quán)值重新分配的方法來證明的.
　　 在本文的最后我們對定向染色的定義進行了

6、推廣，定義了一種新的染色-有向2-路染色．
　　 令m為大于等于1的整數(shù).定向圖G的一個有向m-路k染色f是指一個映射f：V(G)→{1，2，…，k}，滿足：(1)對任意的兩個點x，y，如果1≤(?)(x，y)≤m，則f(x)≠f（y）；(2)任何兩個子集之間的弧都有相同的方向．定向圖G的有向m路色數(shù)xm(G)是指G的所有有向m-路k染色f的最小的k．那么無向圖G的有向m-路色數(shù)xm(G)是它的所有定向圖的有向m-路色數(shù)xm(G