關于一些圖的定向染色.pdf

1、一個定向圖就是指一個無向圖的定向，即給它的每條邊一個方向．本文所說的定向圖都是簡單的有向圖，即無環(huán)或無重弧的有向圖．對一個定向圖，我們用V(G)、A(G)、δ(G)、Δ(G)分別表示圖G的點集、弧集、最小度和最大度，d(v)表示點v的度．如果u、v是圖G中兩個相鄰的點，用uv表示從u到u的弧．G的階數(shù)即為圖G的點數(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個子集（顏色類）的一個剖分，且滿足任何兩個相鄰的點不屬于同一個子集，相當于從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）．
　　 關于圖的定向染色，Kostochka

4、和Sopena等人做了圖的無圈定向色數(shù)的研究，Robert Samal研究了平面圖的強定向染色，Ochem研究了無三角平面圖的定向染色，Borodin等人研究了給定圍長的全體平面定向圖，并在2004年發(fā)表了圍長不限的稀疏圖之間的同態(tài)問題的文章，同時對一個圖的最大平均度與定向色數(shù)之間的關系也作了深入研究．
　　 本文主要研究幾類退化圖，雙外平面圖和特殊平面圖的強定向染色問題，得到如下結果：
　　 定理1令G為2-退化圖，則

5、xs(G)≤7．
　　 定理2令G為3-退化圖，則xs(G)≤19．
　　 定理3令G為4-退化圖，則xs(G)≤67．
　　 定理4令G為雙外平面圖，且G不同構于P，則x8(G)≤19，xs(P)≤67．
　　 定理5設G為平面圖，且G不舍4-7圈，則xs(G)≤19．
　　 對上述問題本文主要是運用可約化的方法和權值重新分配的方法來證明的.
　　 在本文的最后我們對定向染色的定義進行了

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