论文部分内容阅读
染色作为图论研究的一个重要分支,包含了非常丰富的内容,如点染色、边染色、面染色、点边全染色、点边面全染色等等.本文研究的是点染色中的一种特殊形式—均匀染色.我们称图G为均匀k-可染的,如果它的顶点集可以划分成k个独立集,使得任两个独立集的基数之差的绝对值不超过1.而图G的均匀色数是使得图G均匀k-可染的最小正整数k.若对于所有的k≥t,图G是均匀k-可染的,则满足此条件的最小正整数t称为G的均匀色阈. 本文主要分三章:第一章着重介绍了均匀染色理论的来源,“三个猜想”,最新的研究成果以及研究方向;第二章给出了本文所涉及到的基本概念;第三章是本文的重点,分成三节来论证:我们可利用顶点排序的方法,得出由圈上某一点延伸出一条路构成的图,扇图以及轮图,分别与二部图的笛卡尔积图的均匀色数、均匀色阈. 第一节,根据路和圈的顶点个数的奇偶性,得出由圈上某一点延伸出一条路构成的图与完全二部图的笛卡尔积图的均匀色数和均匀色阈至少为2,至多为3. 第二节得出扇图与二部图的笛卡尔积图是均匀4-可染的,并且在某些特殊的情况下它们笛卡尔积图的均匀色阈为3. 第三节得出当轮图的顶点个数为偶数时,轮图与完全二部图的笛卡尔积图的均匀色阈为4,而当轮图顶点个数为奇数时,它们笛卡尔积图的均匀色数至多为4.