English

运筹学学报 ›› 2019, Vol. 23 ›› Issue (2): 31-43.doi: 10.15960/j.cnki.issn.1007-6093.2019.02.003

• 运筹学 • 上一篇    下一篇

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

陶艳亮1, 黄琼湘1,*, 陈琳2   

  1. 1. 新疆大学数学与系统科学学院, 乌鲁木齐 830046;
    2. 新疆医科大学医学工程技术学院, 乌鲁木齐 830011
  • 收稿日期:2017-05-27 出版日期:2019-06-15 发布日期:2019-06-15
  • 通讯作者: 黄琼湘 E-mail:huangqx@xju.edu.cn
  • 基金资助:
    国家自然科学基金（No.11671344）

Contraction graph method for the interval edge-colorings of graphs

TAO Yanliang1, HUANG Qiongxiang1,*, CHEN Lin2   

  1. 1. College of Mathematics and System Science, Xinjiang University, Urumqi 830046, China;
    2. College of Medical Engineering and Technology, Xinjiang Medical University, Urumqi 830011, China
  • Received:2017-05-27 Online:2019-06-15 Published:2019-06-15

PDF

140

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

关键词: 区间边着色, 收缩图, 下界, 双圈图

Abstract: 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 G∈N, 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 introduce a contraction graph method for the interval edge-colorings of graphs. By using this method, we show that w(G)=△(G) or △(G) + 1 for any bicyclic graph G∈N. Moreover, we completely determine bicyclic graphs with w(G)=△(G) and w(G)=△(G) + 1, respectively.

Key words: interval edge-coloring, contraction graph, lower bound, bicyclic graph

中图分类号: