图论最早起源于18世纪三十年代.大数学家Eulcr在1736年完成的关于哥尼斯堡七桥问题的论文，被公认为是研究图论的开山之作.由此，Eulcr也被认为是图论研究的鼻祖.伴随着图论的兴起和发展，这门新兴的学科逐渐在化学、生物学、信息论、控制论、网络理论、博弈论及计算机科学领域产生了广泛的应用.染色理论作为图论最经典的问题之一更是受到了广泛关注.由著名的“四色猜想”开始，染色理论逐步成熟和壮大，先后产生了点染色、边染色、全染色、列表染色、频道染色、条件染色等一系列新的研究方向.在现实生活中染色理论有着广泛的应用背景，如时间表安排问题、工序问题、教室分配问题、选址问题、生产调度问题、频道分配问题等等.　　 本文所考虑的图都是连通的简单有限图.通常情况下，V(G)，E(G)分别表示一个图G的顶点集合和边集合.｜V(G)｜，｜E(G)｜分别表示图G的顶点数和边数，有时也称为图的阶和大小.图G的一个正常k-全染色是指用k种颜色对V∪E中的元素进行着色，使得任何两个相邻接或相关联的元素获得不同的颜色.使得图G存在一个正常k-全染色的最小正整数k称为图G的全色数，记作x(11)(G).若只对图G的顶点（边）进行着色，则称为是图的一个点（边）染色.显然，全染色是对点染色和边染色的推广.　　 Bchzad和Vizing分别在其论文中独立地给出了如下著名的全染色猜想.全染色猜想.对任意图G，都有(11)-(G)≤△+2.尽管围绕着这个猜想已有大量的文献，该问题却至今仍未得到完全解决.　　 本文主要讨论两类新的染色问题，也可以称为两类标号问题，即图的[r，s，t;f]-染色及p，1)-全标号.二者都可以看做是图的全染色的进一步推广.　　 令r，s，t是三个非负整数，f是一个定义在图G的顶点集合V上取值为正整数的函数.图G的一个[r，s，t;f]-染色即给图的每个顶点和每条边都从颜色集C={1，2，…，k}中分配一种颜色使得相邻的顶点获得的颜色差不小于r;每个顶点所关联的边满足(1)获得不同颜色的边的颜色差不小于s并且(2)获得相同颜色的边数不超过f(u);相关联的点和边所获得的颜色差不小于t.我们把使得图存在[r，s，t;f]-染色的最小的颜色数k称为图G的[r，s，t;f]-色数，并记作xr，8，t;f(G).　　 图的[r，s，t;f]-染色是我们首次提出的一个新的染色概念，它可以看作是对[r，s，t]-染色的进一步推广.[r，s，t]-染色的概念最初是由Kcmnitz和Marangio提出的.他们研究了该染色的一些性质并用足球比赛的日程安排问题举例说明了其实际的应用价值。Kcmnitz和Marangio给出了参数xr，8，t(G)的一些上下界并针对参数r，s，t分别取一些特定值的情况得到了一系列的结果.[r，s，t]-染色是一个难度比较大的问题，即使对于星K1,n和完全图Kn等一些简单的图类也没有完全地解决.　　 频道分配问题实质上是一个如何分配无线电频道资源以实现最合理应用的最优化问题.这个课题曾经被AT&T贝尔实验室，美国国家安全局等多个机构的研究部门所研究.在频道分配问题中，我们需要将无线电频率（图论模型中用一些正整数代替）分配给不同的无线电接收装置.为了避免互相干扰而影响信号的传送，如果两个无线电接收装置紧挨着，则要求分配给它们的频率段至少差2，如果两个无线电接收装置靠的比较近但不是紧挨着（比如相隔一个无线电接收装置），则要求分配给它们的频率段至少差1.受这个问题的启发，RogcrYch提出了L(2，1)-标号问题并很快被推广到L(p，q)-标号的形式.　　 图的关联图是指将图G中的每条边都用一条长为2的路代替所形成的新图.Havct将一个图的关联图的L(p，1)-标号问题定义为图的(p，1)-全标号问题.该问题也可以被看作是全染色问题的一种推广形式.一个图G称为是可k-(p，1)-全标号的当且仅当存在一个将V(G)∪E(G)映射到颜色集合{0，1，…，k}的函数c满足:(1)若uu∈E(G)，则｜c（u）-c(u)｜≥1;(2)若e和e′是G的相邻边，则｜c(e)-c(e′)｜≥1;(3)若顶点u和边e相关联，则｜c(u)-c(e)｜≥p.使得G可k-(p，1）-全标号的最小的正整数k称为是图G的(p，1)-全标号数，并记作λTp(G).　　 本文主要讨论图的[r，s，t;f]-染色及(p，1）-全标号.文章的主要内容及结构安排如下.　　 第一章是绪论部分.本章的第一小节是对文中出现和用到的一些基本概念和符号的简单说明，第二小节则分别从全染色，图的[r，s，t卜染色与f-染色和频道分配问题三个方面对论文研究内容的背景做了相对完整的介绍，接下来的第三小节则给出我们所研究的图的[r，s，t;f]-染色及(p，1）-全标号问题的基本定义.最后，本章的第四小节将列出论文中证明的主要结论.　　 第二章主要讨论[r，s，t;f]-染色.在这一章的第一小节中我们先对[r，s，t]-染色的一些背景和已知结果做一个简单的概括，并介绍一些在主要定理的证明中用到的符号和术语.接下来的第二小节是本章的重点部分，在这一节里我们将给出主要的结果及其证明，最后的第三小节接着给出几个可以继续研究的问题.　　 第三章主要讨论图的(p，1)-全标号.第一小节对(p，1)-全标号问题的起源和背景做一个简单的介绍并给出(p，1)-全标号猜想，第二小节主要介绍该问题的研究进展和对于一些特殊图类已经取得的结果，第三小节首先给出一些在主要定理的证明过程中用到的概念和结构性引理，接下来则主要考虑与平面图相关的一些图类的(p，1)-全标号问题，从而为(p，1）-全标号猜想的成立提供新的依据.第四小节将给出关于(p，1）-全标号猜想可以进一步研究的问题.　　 第四章主要讨论图的列表(p，1)-全标号问题.在这一章的第一小节我们先对列表(p，1）-全标号问题做一个总体的介绍，第二小节类比列表全染色猜想给出一个关于列表(p，1)-全标号数上界的猜想，这里不妨称为弱列表(p，1)-全标号猜想，第三小节主要考虑一些特殊图类，如星、外可平面图、可嵌入欧拉示性数为ε的曲面的图等，通过证明这些特殊图类的列表(p，1)-全标号数的上界，进而为我们所提出的弱列表(p，1)-全标号猜想提供依据.最后一小节给出几个值得做进一步研究的问题.