与频道分配有关的两类图染色问题

摘要

图的染色问题是图论的主要研究领域之一，是图论研究中很活跃的一个课题，它在组合分析和实际生活中有广泛的应用。随着科技的发展，经典的各类染色已经不能满足要求，于是产生了许多新的染色。 设G是一个无环边的图．G的顶点正常k染色是指k种颜色1，2，…，k对于G的各顶点的一种分配，使得任意相邻的顶点被染上不同的颜色．令X(G)=min，{k|G是k色可染的)，称X(G)为G的点色数，有时简称为色数，图G的边正常k染色是指k种颜色1，2，…，k对E(G)中元素的一种分配，使得相邻两条边所染颜色不同．令X'(G)=min，{k|G是边k色可染的}称为G的边色数。 Gringgs和Yeh引进了L(2，1)—标号[1]，它的自然推广是L(p，1)—标号[3]．图G的一个L(p，1)—标号是从V(G)到一个整数集合的映射L，必须满足：对于任意的顶点u，v (1)若dG(u，v)=1，贝| L(u)— L(v)|≥p； (2)若dG(u，v)=2，则|L(u)— L(v)|≥1。 图G的L(p，1)—标号在频率分配中有很强的应用背景．Whittleseyet等人在文章[4]中研究了图G的第一剖分图的L(2，1)—标号．图G的第一剖分图s1(G)是图G通过在每条边上加一个点得到的．图s1(G)的L(p，1)—标号对应于从V(G)∪ E(G)到一个整数集合的映射，这个映射必须满足： (1)图G的任意两个相邻的顶点得到不同的整数； (2)图G的任意两个相邻的边得到不同的整数； (3)图G的任意一个顶点和它所关联的边得到的整数必须至少相差p．我们把这种映射称为图G的(p，1)—全标号。 一个(p，1)—全标号的跨度[2]是指最大标号数与最小标号数的差，图G的所有(p，1)—全标号中最小的跨度，称为图G的(p，1)—全标号数[2]，记为λTp(G)．目前对图的(p，1)—全标号的研究还比较初步.Fredeic Havet和Min—Li Yu在文章[2]中给出了λTp(G)的平凡的上下界，提出了(p，1)—全标号猜想：λ(G)≤△(G)+2p-1。 文章[5]中的泛宽度染色是新提出的另一种在频率分配问题上有很强应用的一种染色．泛宽度染色是对点染色的推广，是对图顶点的一种剖分，要求把所有的顶点剖分成宽度两两不同的i—宽度箱Xi，即同一宽度箱Xi中任两点的距离大于i，Xi中的顶点用同一种颜色来染．不同的宽度箱所染的颜色必须两两不同．图G的泛宽度色数Xp(G)=min，{k|G是k—泛宽度可染的}。 在本文第一章中，我们主要介绍了文章所涉及的一些概念、术语和符号和图染色问题的发展情况，在第二章中，我们研究了图的(p，1)—全标号，其中包括外平面图，二部图，正则图，Halin，图以及定义的一种新图．第三章中研究了图的泛宽度染色，给出了二部图和Mycielskian—图的泛宽度色数的最好可能上界，给出了几类特殊图的泛宽度色数．文中主要得到以下结论： 定理2.1.4若图G是一个2—连通外平面图，且不含三角形，△(G)=3，当p≥3时，有λTp(G)=p+3。 定理2.2.2若图G是一个二部图，非正则，△(G)—3，且图G中包含一个相邻于两个最大度点的最大度点，则λT2(G)=5。 定理2.2.4若图G是一个二部图，非正则，△(G)=4，且图G的最大度生成子图G△中包含K1，3，那么λT2(G)=6。 定理2.3.1若p＞X(G)+X'(G)—2，并且图G是边色数X'(G)=△(G)的△—正则图，则λTp(G)=X(G)+X'(G)+p—2。 定理2.3.2若G是一个3—正则图并且含有1—因子，则有λTp(G)≤p+5.定理2.3.3图G是3—正则图，且X(G)=3，p＞3，则λT2(G)≥p+4。 定义2.4.1[38]若对于孓连通平面图G，去掉G中某个面fo的边界上的所有边后，G变成一棵树，并且属于V( fo)的所有顶点的度数是3，那么把G称作Halin图，属于V(fo)的顶点称为G的外部点，其余的顶点称为G的内部点．定理2.4.3图G是一个3—正则Halin，图，则5≤λT2(G)≤6.定理2.4.5图G是一个Halin，图，且△(G)=4，则λT2(G)≤6。 定义2.5.1 G表示任意一个连通图，其中V(G)={v1，v2，…，vn}．G'表示图G的复制图，其中V(G')={v'1，v'2，…，v'n)．新图D(G)是由图G，G'经过下述构造得到的图：把图G中的每个顶点和图G'中所对应的复制点连起来，其中V(D(G))=V(G)∪V(G')，E(D(G))=E(G)∪E(G') U{v1v'1，V2V'2，…，Vnv'n}，不妨称为双图D(G)。 定理2.5.1 Cn表示一个圈，则λT2(D(Cn))=5。 定理2.5.2对于任意的连通图G，满足λT2(G)=△+4，那么双图D(G)的全标号数λT2(D(G))≤λT2(G)+1。 定理3.1.1对任意的自然数m，n，Gm，n是二部图，我们有Xp(Gm，n)≤min{m，n}+1，并且这个上界是最好可能的。 简单图的Mycielskian—图[35]在研究图染色问题的临界性上有重要的应用，我们这里研究简单图的Mycielskian—图的泛宽度染色。 定理3.1.4 G是简单图，且|G|=n．M(G)表示G的Mycielskian—图，则Xp(M(G))≤n+2.并且这个上界是最好可能的。 另外我们还研究了一些特殊图类的泛宽度染色。

目录

文摘

英文文摘

声明

第一章引言

第二章图的(p，1)-全标号

§2.1外平面图的(p，1)-全标号

§2.2二部图的(2，1)-全标号

§2.3正则图的(p，1)-全标号

§2.4 Halin图的(2,1)-全标号

§2.5双图的(2，1)-全标号

第三章图的泛宽度染色

§3.1二部图和Mycielskian-图的泛宽度染色

§3.2几类特殊图的泛宽度染色

§待解决的新问题

参考文献

在学期间发表的学术论文

致谢