中文

Operations Research Transactions ›› 2019, Vol. 23 ›› Issue (2): 31-43.doi: 10.15960/j.cnki.issn.1007-6093.2019.02.003

Previous Articles     Next Articles

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

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

CLC Number: