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

The Lower Bounds of the Interval Edge-Colorings of Infinite Bicyclic Graphs

作　　者：陶艳亮 

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐

出　　处：《应用数学进展》2017年第3期382-387,共6页Advances in Applied Mathematics

摘　　要：图G的一个用了颜色1,2,---t 的边着色称为区间,t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的且这些颜色构成了一个连续的整数区间。图G称为是可区间着色的,如果对某个正整数t,G有一个区间t-着色。所有可区间着色的图构成的集合记作N。对图,使得G有一个区间t-着色的t的最小值和最大值分别记作w(G)和W(G)。本文中,我们证明了对于无穷双圈图,有。An edge-coloring of a graph G with colors 1,2,---t is an interval t-coloring, if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integer. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. The set of all interval colorable graphs is denoted by N . For a graph  , the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G) and W(G), respectively. In this paper, we show for any infinite bicyclic graph .

关 键 词：区间着色 下界 无穷双圈图 

分 类 号：G6[文化科学—教育学]