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.
TAO Yanliang, HUANG Qiongxiang, CHEN Lin
. Contraction graph method for the interval edge-colorings of graphs[J]. Operations Research Transactions, 2019
, 23(2)
: 31
-43
.
DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.003
[1] Asratian A S, Kamalian R R. Interval colorings of edges of a multigraph[J]. Applied Mathematics, 1987, 5:25-34(in Russian).
[2] Asratian A S, Kamalian R R. Investigation on interval edge-colorings of graphs[J]. Journal of Combinatorial Theory, Series B, 1994, 62:34-43.
[3] Petrosyan P A. Interval edge-colorings of complete graphs and n-dimensional cubes[J]. Discrete Mathematics, 2010, 310:1580-1587.
[4] Giaro, ubale KK, MMalafiejski. MConsecutive colorings of t he edges of general graphs[J].i screte D Mathematics, 2001, 236:131-143.
[5] Khachatrian H H, Petrosyan P A. Interval edge-colorings of complete graphs[J]. Discrete Mathematics, 2016, 339:2249-2262.
[6] Kamalian R R, Petrosyan P A. A note on interval edge-colorings of graphs[J]. Mathematical Problems of Computer Science, 2012, 36:13-16.
[7] Zhang W J. Consecutive colorings of the edges of unicyclic and bicyclic graphs[J]. Journal of Xinjiang University (Natural Science Edition), 2006, 23(1):20-24.
[8] Feng YD,H uang. XQConsecutive edge-coloring of t he generalized θ-graph[J].i screteA D pplied Mathematics, 2007, 155:2321-2327.
[9] Petrosyan P A, Khachatrian H H, Tananyan H G. Interval edge-colorings of Cartesian products of graphs[J]. Discussiones Mathematicae Graph Theory, 2013, 33:613-632.
