1. 引言
本文只考虑有限的无向的简单图,设G是一个点集为
,边集为
的图,它的最大度,最小度分别为
,
。对于任意顶点
,令
为G中顶点 的度。对于G的一个全染色
,将
定义为
。
对于任意两个整数
,
。一个t-区间是指t个连续整数组成的集合。设
为G的一个全染色,所使用的颜色集合为
,且每种颜色至少出现一次,若对于每一个顶点
,与v相关联的边以及v本身所使用的颜色构成一个整数区间,则称此全染色为图G的一个t-区间全染色。我们将使得图G存在一个t-区间全染色的最小的和最大的非负整数t分别称为图G的最小区间全色数和最大区间全色数,分别记为
和
。
2005年,Petrosyan在 [1] 中首先给出了图的区间全染色的概念,并且证明了如果
,那么完全二部图
存在t-区间全染色。2008年,Petrosyan和Torosyan在 [2] 中得出了
和
的值以及
的下界。2009年,Petrosyan和Torosyan在 [3] 中得出了
的值。2009年,Petrosyan,Shashikyan和Khachatryan在 [4] [5] 中得出了树的最小区间全色数的上界以及轮图
的
和
的值。2010年,Petrosyan,Shashikyan和Torosyan在 [6] 中得出了
-双正则二部图以及
-双正则二部图都存在区间全染色。2013年,Petrosyan和Khachatryan在 [7] 中证明了路或圈与r-正则图的笛卡尔积分别存在区间全染色。2014年,Petrosyan和Khachatryan在 [8] 中得出了
的上界和
的下界。
2. 主要结果
在展示主要结果前,我们先建立一些引理。
引理1 [9] 如果图G是一个
的2-连通外平面图,则至少有以下之一成立:
(1) 存在相邻的两个2度点u和v;
(2) 存在一个三角面uvw使得
,
。
定理1 如果图G是一个
的外平面图,则
。
证明:我们先考虑
的情况。
情况1 G中不存在割边。
我们对图G的顶点数
进行归纳。对于
,结论显然成立。假设此定理对于图H成立,其中
,
且
。由引理1知:至少有以下之一成立:(1) 存在相邻的两个2度点u和v;(2) 存在一个三角面 使得
,
。因此,我们考虑两种子情况。
情况1.1
且
。
显然,此时G中存在两个不同顶点x,y使得
,
。
情况1.1.1
。
令
,显然,
,且
,
。由归纳假设知:H存在一个区间全染色
且
。
(1)
,即
。
①
。
不失一般性,根据对称性可假设
,
。将边xy删掉,然后分别将边xu,vy和uv染颜色4(2),1(5),3(3)。然后将顶点u和v分别染颜色1(5)和2(4)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
②
。
此时,将边xy删掉,然后分别将边xu,vy和uv染颜色2(4),2(4),3(3)。因为
,所以如果
或
,那么将顶点u和v分别染颜色1(2)和4(5)。否则将顶点u和v分别染颜色4(5)和1(2)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
③
。
此时,将边xy删掉,然后分别将边xu,vy和uv染颜色3,3,4。因为
,所以如果
或
,那么将顶点u和v分别染颜色2和5。否则将顶点u和v分别染颜色5和2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(2)
且
。
①
,
。
在这些情况中,染色规则与(1)中对应相同。
②
。
如果
或
,那么将边xy删掉,然后分别将边xu,vy和uv染颜色2,5,3,将顶点u和v分别染颜色1和4。否则就将边xy删掉,然后分别将边xu,vy和uv染颜色5,1,3,将顶点u和v分别染颜色4和2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(3)
。
①
。
如果
或
,那么将边xy删掉,然后分别将边xu,vy和uv染颜色1,5,3,将顶点u和v分别染颜色2和4。否则就将边xy删掉,然后分别将边xu,vy和uv染颜色5,1,3,将顶点u和v分别染颜色4和2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
②
,
。
在这些情况中,染色规则与(1)中对应相同。
情况1.1.2
。
令
,显然,
且
,由归纳假设知:H存在一个5-区间全染色
。显然此时有:
。
①
。
不失一般性,根据对称性可假设
,
。然后分别将边xu,vy和uv染颜色4(2),4(2),3(3)。然后将顶点u和v分别染颜色5(4)和2(1)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
②
。
(i)
。
不失一般性,根据对称性可假设
,
。然后分别将边xu,vy和uv染颜色4(2),4(2),3(3)。然后将顶点u和v分别染颜色2(1)和5(4)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(ii)
,
。
因为
且
,所以可以分别将边xu,vy和uv染颜色4(5),1(2),3(3)。然后将顶点u和v分别染颜色5(4)和2(1)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(iii)
。
不失一般性,根据对称性可假设
,
。这两种子情况可以用相同的染色方法。因为
且
,所以分别将边xu,vy和uv染颜色5,1,3。然后将顶点u和v分别染颜色4和2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
③
。
(i)
。
不失一般性,根据对称性可假设
,
。这种情况下,染色规则与情况1.1.2中②(i)的对应情况一样。
(ii)
,
。
如果
且
,染色规则与情况1.1.2中②(ⅱ)的对应情况一样。否则就分别将边xu,vy和uv染颜色4,5,3。然后将顶点u和v分别染颜色2和4。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(iii)
,
。
因为
且
,所以分别将边xu,vy和uv染颜色4,2,3。然后将顶点u和v分别染颜色5和1。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(iv)
。
不失一般性,根据对称性可假设
,
。染色规则与情况1.1.2中②的对应情况一样。
(v)
,
。
如果
且
,那么将边xy删掉,然后分别将边xu,vy和uv染颜色5,2,3,将顶点u和v分别染颜色4和1。否则就将边xy删掉,然后分别将边xu,vy和uv染颜色1,2,3,将顶点u和v分别染颜色2和1。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
情况1.2
,且
,
。
令
,显然,
且
,由归纳假设知:H存在一个5-区间全染色
。我们考虑边uw的颜色
。由于
,所以G中存在一个顶点
。同理存在一个顶点
。
情况1.2.1
。
不失一般性,根据对称性可假设
,
。如果
,那么将顶点u的颜色改为颜色4(2),然后将边uv,vw和顶点v分别染颜色3(3),4(2),5(1)。否则就将顶点u和边uw的颜色改为颜色5(1)和4(2),然后将边uv,vw和顶点v分别染颜色3(3),5(1),4(2)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
情况1.2.2
。
(1)
。
不失一般性,根据对称性可假设
,
。如果
,那么将顶点w (u)的颜色改为颜色4(2),然后将边uv,vw和顶点v分别染颜色4(3),3(2),2(4)。否则就将顶点w(u)和边uw的颜色分别改为颜色2(4)和4(2),然后将边uv,vw和顶点v分别染颜色2(3),3(4),4(2)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(2)
,
。
①
且
。
如果
,那么将顶点w (u)的颜色改为颜色5 (1),然后将边uv,vw和顶点v分别染颜色4(3),3(2),2(4)。如果
且
,那么将顶点u,w和边uw的颜色分别改为颜色4(4),2(2)和1(5),然后将边uv,vw和顶点v分别染颜色2(3),3(4),1(5)。如果
且
,那么将顶点u和w的颜色分别改为颜色5(5)和1(1),然后将边uv,vw和顶点v分别染颜色4(3),3(2),2(4)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
②
且
。
因为
且
,所以将边uv,vw和顶点v分别染颜色4(1),5(2),3(3)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
③
且
。
如果
且
,那么将顶点u和w的颜色分别改为颜色4(1),5(2),然后将边uv,vw和顶点v分别染颜色3(2),4(3),2(4)。如果
且
,那么将顶点u,w和边uw的颜色分别改为颜色2(1),5(4)和4(2),然后将边uv,vw和顶点v分别染颜色3(4),2(3),4(2)。如果
且
,那么将顶点u和w的颜色分别改为颜色4(5),1(2),然后将边uv,vw和顶点v分别染颜色3(2),4(3),2(4)。如果
且
,那么将顶点u,w和边uw的颜色分别改为颜色2(5),1(4)和4(2),然后将边uv,vw和顶点v分别染颜色3(4),2(3),4(2)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(3)
。
不失一般性,根据对称性可假设
,
。如果
,那么将顶点u (w)的颜色改为颜色1(5),然后将边uv,vw和顶点v分别染颜色3(5),1(3),2(4)。否则就将顶点u (w)的颜色改为颜色5(1),然后将边uv,vw和顶点v分别染颜色3(5),1(3),2(4)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
情况1.2.3
。
(1)
。
不失一般性,根据对称性可假设
,
。如果
,那么将顶点w的颜色改为颜色4,然后将边uv,vw和顶点v分别染颜色4,2,3。否则就将顶点w和边uw的颜色分别改为3,4,然后将边uv,vw和顶点v分别染颜色3,2,4。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(2)
,
。
因为
且
,所以将边uv,vw和顶点v分别染颜色4(4),5(2),3(3)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(3)
。
不失一般性,根据对称性可假设
,
。如果
,那么将顶点u的颜色改为颜色5,然后将边uv,vw和顶点v分别染颜色2,1,3。否则就将顶点u的颜色改为颜色1,然后将边uv,vw和顶点v分别染颜色2,1,3。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(4)
,
因为
且
,所以将边uv,vw和顶点v分别染颜色1,2,3。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
(5)
。
不失一般性,根据对称性可假设
,
。如果
,那么将顶点w的颜色改为颜色2,然后将边uv,vw和顶点v分别染颜色2,1,3。否则就将顶点w和边vw的颜色分别改为3,2,然后将边uv,vw和顶点v分别染颜色3,1,2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所获得的全染色是G的一个5-区间全染色。
情况2 G中存在割边。
显然,G中存在某条割边与一个2-连通块B关联。
情况2.1
。
此时,我们可以在块B中借助数学归纳法证明此定理,方法情况1与一样。
情况2.2
。
令顶点w是块B与割边的公共顶点。显然
。令
,令x为距离顶点w最近的3度点。我们先假设x不在圈上。
情况2.2.1x与顶点w相邻。
对
进行归纳。如果
,定理成立。假设此定理对于图H成立,其中
,
且
。令
。显然,
且
,
。由归纳假设知:H存在一个5-区间全染色
。令
。
(1)
。
如果
,那么将顶点u,v和w分别染颜色4,3,2,然后将边uw,vw和uv分别染颜色3,4,2。否则就将顶点u,v和w分别染颜色4,2,3,然后将边uw,vw和uv分别染颜色2,4,3。
(2)
。
存在两个正整数b,c使得
,其中
且
。如果
,那么将顶点u,v和w分别染颜色c,b,1,然后将边uw,vw和uv分别染颜色b,c,a。如果
且
,那么将顶点u,v和w分别染颜色3,1,4,然后将边uw,vw和uv分别染颜色1,3,2。如果
且
,那么将顶点u,v和w分别染颜色2,1,4,然后将边uw,vw和uv分别染颜色1,2,3。
情况2.2.2顶点x与顶点w之间是一条路
。令
,其中
,
。
1.
。
给图G定义一个全染色
:
(1) 对于任意
,
(2) 对于任意
,
如果
,那么交换(1)中染颜色2和3的顶点的颜色,且同时交换(2)中染颜色2和3的边的颜色。显然
或2或3。
①
。
如果
,那么将顶点u,v和w分别染颜色4,2,3,然后将边uw,vw和uv分别染颜色2,4,3。如果
,那么将顶点u,v和w分别染颜色4,3,2,然后将边uw,vw和uv分别染颜色3,4,2。
②
。
因为
,所以将顶点u,v和w分别染颜色3(2),1(1),4(4),然后将边uw,vw和uv分别染颜色1(1),3(2),2(3)。
2.
。
在1中的(1)和(2)的基础上,交换(1)中染颜色1(1)和2(3)的顶点的颜色,且同时交换(2)中染颜色1(1)和2(3)的边的颜色。假设新得到的全染色为
。如果
,那么在
的基础上,交换(1)中染颜色1(1)和3(2)的顶点的颜色,且同时交换(2)中染颜色1(1)和3(2)的边的颜色。显然
或2或3
。在各种子情况下,染色规则与1中①②③分别对应相同。
3.
。
给图G定义一个全染色
:
(1) 对于任意
,
(2) 对于任意
,
如果
,那么交换(1)中染颜色2和3的顶点的颜色,且同时交换(2)中染颜色2和3的边的颜色。显然
或3或4。
①
或3。
因为
,所以将顶点u,v和w分别染颜色4,3,1,然后将边uw,vw和uv分别染颜色3,4,2。
②
。
因为
,所以将顶点u,v和w分别染颜色3,2,1,然后将边uw,vw和uv分别染颜色2,3,4。
4.
。
给图G定义一个全染色
:
(1) 对于任意
,
(2) 对于任意
,
如果
,那么交换(1)中染颜色3和4的顶点的颜色,且同时交换(2)中染颜色3和4的边的颜色。显然
或4或5。
①
。
因为
,所以将顶点u,v和w分别染颜色4(3),2(2),1(1),然后将边uw,vw和uv分别染颜色2(2),4(3),3(4)。
②
。
因为
,所以将顶点u,v和w分别染颜色4,3,2,然后将边uw,vw和uv分别染颜色3,4,2。
最后,我们考虑顶点x在圈上。令此圈为
且
,其中
。
情况2.2.3x与顶点w相邻。我们先染此圈。
1.
,
。
给图
定义一个全染色
:
(1) 对于任意
,
(2) 对于任意
,
(3)
。
2.
,
且t为奇数。
给图
定义一个全染色
:
(1) 对于任意
,
(2) 对于任意
,
(3)
。
3.
,
且t为偶数。
给图
定义一个全染色
:
(1) 对于任意
,
(2) 对于任意
,
(3)
。
显然,
且
。所以我们可以将边
染颜色4,然后将顶点u,v和w分别染颜色2,1,3,然后将边uw,vw和uv分别染颜色1,2,3。
情况2.2.4x与顶点w之间是一条路。令此路为
且
,其中
,
。
先用情况2.2.3中同样的方法染圈
。然后将边
染颜色4。对于剩余顶点与边,染色规则与情况2.2.2中4的方法一样。
情况2.3
。
令顶点w是块B与割边的公共顶点。显然
。令
,顶点y是x和z的公共顶点。如果边
,那么染色规则与情况1一样。因此我们只需考虑
。令
为距离顶点w最近的3度点。我们先假设
不在圈上。
情况2.3.1 顶点w与
相邻。
对
进行归纳。如果
,定理显然成立。假设对于任意的外平面图H来说,定理成立,其中
且
,
。令
,由归纳假设知:H存在一个5-区间全染色点
。令
。
(1)
。
如果
,那么将顶点x,y,z和w分别染颜色5,2,5,2,然后将边xw,xy,yz和zw分别染颜色3,4,3,4。否则就将顶点x,y,z和w分别染颜色1,4,1,4,然后将边xw,xy,yz和zw分别染颜色2,3,2,3。
(2)
。
如果
,那么将顶点x,y,z和w分别染颜色2(4),5(1),2(3),1(1),然后将边xw,xy,yz和zw分别染颜色3(2),4(3),3(2),4(4)。否则就将顶点x,y,z和w分别染颜色2(2),5(5),2(3),4(4),然后将边xw,xy,yz和zw分别染颜色1(1),3(3),4(4),3(2)。
(3)
。
如果
,那么将顶点x,y,z和w分别染颜色4,1,4,1,然后将边xw,xy,yz和zw分别染颜色2,3,2,3。否则就将顶点x,y,z和w分别染颜色4,1,4,5,然后将边xw,xy,yz和zw分别染颜色2,3,2,3。
情况2.3.2顶点
与顶点w之间是一条路
。令
,其中
,
。
1.
。
给图G定义一个全染色
:
(1) 对于任意
,
(2) 对于任意
,
如果
,那么交换(1)中染颜色2和3的顶点的颜色,且同时交换(2)中染颜色2和3的边的颜色。显然
或2或3。
①
。
因为
,那么将顶点x,y,z和w分别染颜色1,4,1,4,然后将边xw,xy,yz和zw分别染颜色2,3,2,3。
②
。
因为
,那么将顶点x,y,z和w分别染颜色2(2),5(5),2(3),4(4),然后将边xw,xy,yz和zw分别染颜色1(1),3(3),4(4),3(2)。
2.
。
在1中(1)和(2)的基础上,交换(1)中染颜色1(1)和2(3)的顶点的颜色,且同时交换(2)中染颜色1(1)和2(3)的边的颜色。假设新得到的全染色为
。如果
,那么在
的基础上,交换(1)中染颜色1(1)和3(2)的顶点的颜色,且同时交换(2)中染颜色1(1)和3(2)的边的颜色。显然
或2或3
。在各种子情况下,染色规则与1中①②③分别对应相同。
3.
。
给图G定义一个全染色
:
(1) 对于任意
,
(2) 对于任意
,
如果
,那么交换(1)中染颜色2和3的顶点的颜色,且同时交换(2)中染颜色2和3的边的颜色。显然
或3或4。因为
,所以我们使用情况2.3.1中对应情况的染色规则来染剩余顶点与边。
4.
。
给图G定义一个全染色
:
(1) 对于任意
,
(2) 对于任意
,
如果
,那么交换(1)中染颜色3和4的顶点的颜色,且同时交换(2)中染颜色3和4的边的颜色。显然
或4或5。因为
且
,所以我们使用情况2.3.1中对应情况的染色规则来染剩余顶点与边。
最后,我们考虑顶点
在圈上。令此圈为
且
,其中
。
情况2.3.3
且
与w相邻。
先用情况2.2.3中染圈
的方法来染圈
。然后将边
染颜色4。对于剩余顶点与边,染色规则与情况2.3.1中(4)的方法一样。
情况2.3.4
与顶点w之间是一条路。令此路为
且
,其中
,
。
先用情况2.2.3中染圈
的方法来染圈
。然后将边
染颜色4。对于剩余顶点与边,染色规则与情况2.3.2中3的方法一样。
最后我们考虑
,即图G中存在叶子点,将其中一个叶子点记为u,将顶点u的邻点记为v。对图G顶点数
进行归纳,如果
,定理显然成立。假设对于任意的外平面图H来说,定理成立,其中
且
,
。令
,由归纳假设知:H存在一个5-区间全染色点
。
情况3
。
(1)
或
。
因为
,
,所以我们可以将边uv和顶点u分别染颜色
,
。
(2)
或
。
因为
,
,所以我们可以将边uv和顶点u分别染颜色
,
。
情况4
。
(1)
。
因为
,所以将边uv和顶点u分别染颜色4(2),5(1)。
(2)
。
如果
,所以将边uv和顶点u分别染颜色1,2。否则就将边uv和顶点u分别染颜色5,4。
情况2,情况3和情况4中剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然,所得到的全染色均为图G的一个5-区间全染色且
。 £