论文摘要
染色问题是图论研究的经典领域，它源自于四色定理的研究，是图论研究中一个很活跃的课题。随着染色问题在现实中被广泛应用，各类染色问题被相继提出并加以发展、应用。图G的一个（正常）k-染色是将k种染色分配给G的顶点集V（G），使得相邻两顶点的颜色不同。定义色数为：x（G）=min{k|图G有k-染色}。类似的，图G的一个（正常）k-边染色是将k种染色分配给G的边集E（G），使得有公共端点的两边的颜色不同。边色数x′（G）=min{k|图G有k-边染色}。全染色的概念是对点染色和边染色的推广，是图论染色的一个传统问题，由Vizing（1964）和Behzad（1965）各自独立提出的。图的全染色是对图的点，边进行染色，使得相邻或相关联的两元素染色不同。图的全色数xT（G）=min{k|图G有一个k-全染色}。在全染色的基础上，张忠辅提出了邻点可区别的全染色的概念并给出了相应的猜想和两个引理。张忠辅定义的邻点可区别的全染色如下：设G（V，E）为阶不小于2的简单连通图，k为正整数，令映射f：V（G）∪E（G）→{1，2，…，k}。对任意u∈V（G），如果（1）对任意uv，vw∈E（G），u≠w，有f（uv）≠f（vw）。（2）对任意uv∈E（G），有f（u）≠f（v），f（u）≠f（uv），f（uv）≠f（v）。则称f为图G的一个k-全染色，简记为k-TC。若还满足（3）对任意uv∈E（G），C（u）≠C（v），其中C（u）={f（u）}∪{f（uv）|uv∈E（G）}。那么称f为图G的一个k-邻点可区别全染色，简记为k-AVDTC。图G的全色数xT（G）（或记为x″（G））=min{k|图G有k-全染色}。图G的邻点可区别的全色数xat（G）=min{k|图G有k-AVDTC}。张忠辅给出了关于邻点可区别全染色的两个引理：对任意阶为n（n≥2）的简单连通图G，邻点可区别全色数xat（G）存在，并且xat（G）≥△（G）+1。若图G（V，E）有两个相邻的最大度点，则有xat（G）≥△（G）+2。张忠辅在文献中给出了邻点可区别全色数猜想：对任意阶为n（n≥2）的简单连通图G，有xat（G）≤△（G）+3。确定一任意给定图的邻点可区别全色数是NP-困难的。目前关于路，圈，完全图，完全二部图，星，扇，轮，树等特殊图的邻点可区别全色数已给出。另外上述特殊图的Mycielski图，联图和乘积图的邻点可区别全色数已有一些结果。同时，Petersen图，Heawood图，Thomassen图的邻点可区分全色数也已得到结果。1880年，边染色的概念被提出，在边染色问题的研究中有著名的四色定理。1964年，Vizing得出一个重要的定理即对任意的简单图G，有△（G）≤x′（G）≤△（G）+1。1974年，R．P．Gupta对边覆盖染色进行了研究。图G的边覆盖染色是对图G的所有边进行染色使得每种颜色在每个顶点上至少出现一次。满足图G有一个k-边覆盖染色的最大正整数k称为图G的边覆盖色数，记为x′c（G）。同年，Gupta证明了对任意的简单图G，有δ（G）-1≤x′c（G）≤δ（G）。若x′c（G）=δ（G），则称G是第一类的。若x′c（G）=δ（G）-1，则称G是第二类的。刘桂珍老师及苗连英，宋惠敏等对图的边覆盖染色进行了进一步的研究并取得了丰硕的成果。2006年，孙磊老师受边覆盖染色的启发提出了全色极大团染色的概念。全色极大团染色是对图G的顶点进行染色，使得G的每个极大团所有颜色均出现。满足图G有一个k-全色极大团染色的最大正整数k称为图G的全色极大团色数，记为xmaxcT（G）。显然有xmaxcT（G）≤min{|H||H为G的极大团}。本文一部分主要探讨了轮，完全图的Hajós sum的邻点可区别全色数。另外还得到了特殊图Pnk，花G的邻点可区别全色数。另一部分讨论了特定条件下全色极大团染色与边覆盖染色的等价性，给出了联图，复合图，笛卡尔乘积图，外平面图的全色极大团色数，并给出了Kn-M，Cn，Mycielski图，类Mycielski图的全色极大团色数。在本文中，我们主要得到结论如下：两个点不交的图G1和G2的Hajós sum G=（G1，x1y1）+（G2，x2y2）是由G1∪G2粘合x1，x2为一个点，删去边x1y1，x2y2增加边y1y2所得。其中x1y1∈E（G1），x2y2∈E（G2）。令Wn=K1∨Cn，V（Wn）={v1，v2，…，vn，v0)，E（Wn）={vivi+1|i=1，2，…，n；vn+1=v1}∪{v0vi|i=1，2，…，n}，W′n为Wn的复制。定理2．1．1 Hajós sum Wn*=（Wn，v1v2）+（W′n，v′1v′2），粘合v1，v′1为一个点v1，则定理2．1．2 Hajós sum G=（Wn，v0v1）+（W′n，v′0v′1），粘合v0，v′0为一个点v0，则xat（G）=2n-1。定理2．1．3 Hajós sum G=（Km，v1v2）+（Kn，v′1v′2），粘合v1，v′1为一个点v1，则在含有n个顶点的路Pn上，当且仅当两点距离为k时添加一条边，所得的图称为Pnk图。定理2．2．1对图Pnk，k=[n/2]，有Xat（Pnk）=5。Kn是具有n个顶点v1，…vn的完全图，在Kn的每个顶点vi上悬挂mi（1≤i≤n）个点vi1，…，vimi，这mi个点形成一条路vi1vi2…vimi，如此得到花G。定理2．2．2对花G，不妨设ms=maxk=1，2…n mk，有对任意的图G，其线图L（G）的顶点集为E（G），两点之间有边当且仅当在图G中两边相邻。对任意的图G，其全图T（G）的顶点集为V（G）∪E（G），两元素间有边当且仅当在图G中两元素相邻或相关联。记p=min{|G′||G″为G的极大团}。q=min{|H′||H′为H的极大团}。定理3．1．1若存在H使G=L（H）且p≥4。则图G的全色极大团染色等价于图H的边覆盖染色。Gupta定理的内容是对任意的简单图G。有δ（G）-1≤x′c（G）≤δ（G）。推论3．1．2 Gupta定理等价于下面两种情形：（1）若存在H使G=L（H）且p≥4，则有p-1≤xmaxcT（G）≤p。（2）若存在H使G=T（H）且p≥4，则有p-1≤xmaxcT（G）≤p。M是完全图Kn的某一匹配，则Kn-M的所有极大团点数相同，均为n-2|M|+|M|=n-|M|，且Kn-M的每个极大团的点集形式为V（Kn）＼V（M）与|M|个点的并集，这|M|个点是从M的每个匹配边连结的两点中任意一点组成的。定理3．1．3完全图Kn，N（?）E（Kn）且δ（Kn-N）≥n-2，则xmaxcT（Kn-N）=n-|N|。定理3．1．4 G=Cn，则两个图G和H的联图G∨H定义为：V（G∨H）=V（G）∪V（H），E（G∨H）=E（G）∪E（H）∪{uv|u∈V（G）。v∈V（H）}。定理3．1．5对任意简单连通图G，H，有xmaxcT（G∨H）=xmaxcT（G）+xmaxcT（H）。两个图G和H的复合图G[H]定义为：它的顶点集为V（G）×V（H），其中两个顶点（u，v），（u′，v′）相邻当且仅当或者uu′∈E（G），或者u=u′，vv′∈E（H）。定理3．1．6图G，H分别满足xmaxcT（G）=p，xmaxcT（H）=q，则有xmaxcT（G[H]）=xmaxcT（G）xmaxcT（H）。并不是对所有的简单连通图G，H均有xmaxcT（G[H]）=xmaxcT（G）xmaxcT（H）。例如：G=Pn，H=C2m+1，而xmaxcT(Pn[C2m+1]=3≠2×1。对于图G和H，设V（G）={u1，u2，…，um}，V（H）：{v1，v2，…，vn}。它们的笛卡尔乘积G×H定义为：V（G×H）={wij=（ui，vj），1≤i≤m，1≤j≤n}，E（G×H）={wijwkl，i=k和vjvl∈E（H）或j=l和uiuk∈E（G）}。定理3．1．7若p-1≤xmaxcT（G）≤p，q-1≤xmaxcT（H）≤q，则有xmaxcT（G×H）=min{xmaxcT（G），xmaxcT（H）}。我们称由Mycielski作图法得到的图为Mycielski图。给定图G，其顶点集V={v1，v2，…，vn}。图G的Mycielski图（记为M（G））定义为：顶点集V（M（G））=V∪{v′1，v′2，…，v′n，w}，边集E（M（G））=E（G）∪{viv′j|vivj∈E（G），i，j=1，…，n}∪{v′iw|i=1，…，n}。定理3．2．1对任意简单连通图G，均有xmaxcT（M（G））=1。定理3．2．2对任意简单连通图G，令u（G）=M（G）-w，则xmaxcT（u（G））=xmaxcT（G）。给定图G，顶点集为V={v1，v2，…，vn}。图G的类M构造图（记为S（G））定义如下：V（S（G））=V（G）∪V（G′）∪{w}，G′为G的复制。边集E（S（G））=E（G）∪E（G′）∪{viv′i|vi∈V（G），i=1，2，…，n}∪{viv′j|vivj∈E（G），i，j=1，2，…n}∪{v′iw|i=1，2，…，n}。对图Sm（G）定义为：S1（G）=S（G）。V（Sm（G））=V（G）∪V（G′）∪V（G″）∪…∪V(G（m）∪{w}，E（Sm（G））=E（G）∪E（G′）∪E（G″）∪…∪E(G（m）)∪{vi（j）vi（j+1）|vi∈V（G），i=1，2，…，n；j=0，1，…，m-1；vi（0）=vi}∪{vi（k）vj（k+1）|vivj∈E（G），i，j=1，2，…，n；k=0，1，…，m-1}∪{vi（m）w|vi∈V（G），i=1，2，…，n}。定理3．2．3对任意简单连通图G，有xmaxcT（S（G））=xmaxcT（G）+1。推论3．2．4令S0（G）=G∨{w}，则有xmaxcT（S0（G））=xmaxcT（G）+1。定理3．2．5对任意简单连通图G，有xmaxcT（Sm（G））=xmaxcT（G）+1。定理3．2．6若G为外平面图且p=2，则定理3．2．7若G为外平面图且p=3，则xmaxcT（G）=3。
论文目录
相关论文文献
标签：全染色论文; 邻点可区别全染色论文; 边覆盖染色论文; 全色极大团染色论文;