图的区间边着色的收缩图方法

图G的一个用了颜色1,2,…,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的,且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作■.对图G∈■,使得G有一个区间t-着色的t的最小值和最大值分别记作ω(G)和W(G).现给出了图的区间着色的收缩图方法.利用此方法,我们对双圈图G∈■,证明了ω(G)=△(G)或△(G)+1,并且完全确定了ω(G)=△(G)及ω(G)=△(G)+1的双圈图类.

无穷双圈图的区间边着色的下界

图G的一个用了颜色1,2,---t 的边着色称为区间,t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的且这些颜色构成了一个连续的整数区间。图G称为是可区间着色的,如果对某个正整数t,G有一个区间t-着色。所有可区间着色的图构成的集合记作N。对图,使得G有一个区间t-着色的t的最小值和最大值分别记作w(G)和W(G)。本文中,我们证明了对于无穷双圈图,有。