论文部分内容阅读
一个定向图就是指一个无向图的定向,即给它的每条边一个方向.本文所说的定向图都是简单的有向图,即无环或无重弧的有向图.对一个定向图,我们用V(G)、A(G)、δ(G)、Δ(G)分别表示图G的点集、弧集、最小度和最大度,d(v)表示点v的度.如果u、v是图G中两个相邻的点,用uv表示从u到u的弧.G的阶数即为图G的点数.
假设G和H是两个有向图,那么从G到H的一个同态是指一个作用在V(G)到V(H)的一个映射Ψ,满足:(x,y)∈E(G)(→)(Ψ(x),Ψ(y))∈E(H),则称H是G的一个目标图,记作G→H.
图H的一个k-正常染色是指将图H的点集分成k个子集(颜色类)的一个剖分,且满足任何两个相邻的点不属于同一个子集,相当于从H到完全图Kk的一个同态,那么图H的染色教x(H)就可以定义为H的所有k-正常染色中最小的k即k满足H→Kk,H(?)Kk-1.
一个定向图G的一个k-定向染色是指将点集V(G)分成k个子集(颜色类)的一个剖分,且满足:(1)任何两个相邻的点不属于同一个子集;(2)任何两个子集之间的弧都有相同的方向,同样定向图G的定向色数xo(H)可以定义为G的所有k-定向染色中最小的k,即k为满足G→H的所有定向图H的最小阶,也就是G的所有目标图的最小阶.对于一个无向图,它的定向色数是指它的所有定向中的最大的定向色数.其中强定向染色是指目标图为Cayley图的定向染色,强定向染色数记为xs(H).
关于图的定向染色,Kostochka和Sopena等人做了图的无圈定向色数的研究,Robert Samal研究了平面图的强定向染色,Ochem研究了无三角平面图的定向染色,Borodin等人研究了给定围长的全体平面定向图,并在2004年发表了围长不限的稀疏图之间的同态问题的文章,同时对一个图的最大平均度与定向色数之间的关系也作了深入研究.
本文主要研究几类退化图,双外平面图和特殊平面图的强定向染色问题,得到如下结果:
定理1令G为2-退化图,则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.
对上述问题本文主要是运用可约化的方法和权值重新分配的方法来证明的.
在本文的最后我们对定向染色的定义进行了推广,定义了一种新的染色-有向2-路染色.
令m为大于等于1的整数.定向图G的一个有向m-路k染色f是指一个映射f:V(G)→{1,2,…,k},满足:(1)对任意的两个点x,y,如果1≤(?)(x,y)≤m,则f(x)≠f(y);(2)任何两个子集之间的弧都有相同的方向.定向图G的有向m路色数xm(G)是指G的所有有向m-路k染色f的最小的k.那么无向图G的有向m-路色数xm(G)是它的所有定向图的有向m-路色数xm(G)中的最大值.当m=2时,即为有向2-路染色.
根据Halin图的有向2-路色数小于等于7的结论,我们对2-退化图的有向2-路色数作了猜想:
猜想如果G是一个2-退化图,则x2(G)≤5.