扇图与轮图的［r，s，t］

扇图与轮图的［r，s，t］－着色

2014-10-10张新军

长春工业大学学报 2014年4期

张新军

（莆田学院数学学院，福建莆田 351100）

0 引言

图的着色理论是图论中一个非常重要的分支，有广泛的应用，如排课表问题、存储问题、电路安排问题、交通问题、频道分配问题等。作为一般点着色、边着色和全着色的推广，2007年，A.Kemnitz和 M.Marangio［1－2］提出了图的［r，s，t］－着色和［r，s，t］－色数的定义，给出有关的一些性质、定理，并讨论完全图的［r，s，t］－色数。在文献［3－4］中讨论了二部图和树路的［r，s，t］－色数，在文献［5－7］中分别讨论圈和星图的［r，s，t］－色数，文献［8］给出了超图的［r，s，t］－着色和［r，s，t］－色数。文中主要讨论了扇图和轮图的［r，s，t］－色数。

1 预备知识

文中所涉及的图G均为简单有限连通图，Δ（G）＝Δ表示图G（V，E）的最大度，VΔ表示由最大度顶点的集合，χ（G），χ′（G），χ″（G）和χr，s，t（G）分别表示点色数、边色数、全色数和［r，s，t］－色数，未定义的符号和术语可参见文献［9］。

下面给出［r，s，t］－着色和［r，s，t］－色数的定义：

定义1［1］给定非负整数的r，s和t，且max｛r，s，t｝≥1，图G（V，E）的一个k－［r，s，t］－着色是指从V（G）∪E（G）到｛0，1，…，k－1｝，k∈N的一个映射c，如果c满足下列条件：

1）对V 中相邻的点vi，vj，有｜c（vi）－c（vj）｜≥r；

2）对E中相邻的点ei，ej，有｜c（ei）－c（ej）｜≥s；

3）对V∪E中相关联的点vi和边ej，有｜c（vi）－c（ej）｜≥t。

则称c为G 的一个［r，s，t］－着色。

定义2［1］使得图G 存在［r，s，t］－着色的最小的值k，称为图 G 的［r，s，t］－色数，记作χr，s，t（G）。

显然，［r，s，t］－着色是对点着色、边着色和全着色的推广，因为［1，0，0］－着色是正常的点着色，［0，1，0］－着色是正常的边着色，［1，1，1］－着色是正常的全着色，即

下面几个引理是文献［1］得到的部分结论。

引理1［1］若 H⊆G，则χr，s，t（H）≤χr，s，t（G）。

引理2［1］若r′≤r，s′≤s，t′≤t，则

引理3［1］

2 主要结果及证明

定义3 扇图Fn＝Pn－1＋O1，其中Pn－1为n－1阶的路，O1为一个孤立点。

定理1 若G＝Fn（n≥4），则

1）

2）

3）当s≥2时，χ1，s，1（Fn）＝（Δ－1）s＋1。

4）χ1，1，t（Fn）＝Δ＋t＋1。

证明：

其余的边可用t和t＋s交替着色。所以

又

故

当（Δ－1）s≥2r＋2t且s≥2t，r≥2s时，有（Δ－1）s－（2r＋t）≥t，s－t≥t且r＋t－2s≥t，于是可对Fn进行如下的［r，s，t］－着色：

其余的边可用0和s交替着色。所以

又

所以

然后进行检验，如果发现有两条边和它对应的端点的颜色相同，则可以互换这两条边的颜色；若只有一条边的颜色和端点的颜色相同，则可将这条边的颜色和着2r的这个顶点所对应的边的颜色互换。这样总共用Δ＋1种颜色，即χr，1，1（Fn）≤Δ＋1，又由引理2知

所以

3）由引理 2 知，χ1，s，1（Fn）≥χ0，s，0（Fn）＝（Δ－1）s＋1。当n＝4时，因为s≥2，所以2s－1≠s，2s≠2，可进行如下着色：

所以

因此

当n≥5时，因为s≥2，所以2s－1≠s，3s－1≠2s，于是可进行如下着色，如图1所示。

图1 当n≥5，s≥2时扇图的［1，s，1］－着色

所以

4）因为G＝Fn且n≥4，所以

由引理3知

当n＝4时，因为r＝s＝1，t≥1，所以可进行如下着色：

共需t＋4＝Δ＋t＋1种颜色。于是

考虑K1，3：对K1，3来说，因为Δ＝3，所以如果要对其进行［1，1，t］－着色，则需要t＋4种颜色。而由引理1知

所以

当n≥5时，可进行如下着色：

其余的边可用t＋2和t＋3进行交替着色。这样就得到一个［1，1，t］－着色。即

由引理1知

所以

综上所述，χ1，1，t（Fn）＝Δ＋t＋1。

下面研究轮图的［r，s，t］－色数。

定义4 轮图Wn＝Cn－1＋O1，其中Cn－1表示长度为n－1的圈。

当n≥7为奇数时，有如下定理成立。

定理2 设G＝Wn（n为奇数，n≥7），则

1）

2）

3）当s≥2时，χ1，s，1（Wn）＝（Δ－1）s＋1。

4）

证明

且

于是可以进行如下着色（当n＝9时）如图2所示。

图2 当n＝9时轮图的［r，s，t］－着色

又所以

χr，s，t（Wn）＝2r＋1

因为

且s≥2t，所以

所以可以进行如下着色：

另一方面

所以

2）因为G＝Wn（n为奇数，n≥7），所以

由引理2知

所以

当n≥6为偶数时，有如下定理成立。

定理3 设G＝Wn（n为偶数，n≥6），则

1）

2）

3）当s≥2时，χ1，s，1（Wn）＝（Δ－1）s＋1。

4）

证明

于是可以进行如下着色：

其余的边可用t，t＋s和t＋2s这3种颜色进行着色，所以

又由引理2知

所以

因为

且

所以

于是可以作如下着色，如图3所示。

图3 当n＝10时轮图的［r，s，t］－着色

又因为

所以

2）因为n（n≥6）为偶数，所以

然后检验轮辐，如果只有一条边的颜色和端点的颜色相同，则可将这条边的颜色和着2r的这个顶点所对应的边的颜色互换，如果有两条边和它对应的端点的颜色相同，则可以互换这两条边的颜色；如果有3条边和它对应的端点的颜色相同，则可以轮换这3条边的颜色，使这3条边和它们对应的端点的颜色不同；最后，对e′n－1这条边可以用｛0，1，…，Δ｝／｛0，1，c（eΔ），r，2r｝（c（eΔ）表示边eΔ所用的颜色）中的一种颜色进行着色，这样总共用Δ＋1种颜色。即