English

运筹学学报 >

2019 , Vol. 23 >Issue 2: 31 - 43

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.02.003

运筹学

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

展开
  • 1. 新疆大学数学与系统科学学院, 乌鲁木齐 830046;
    2. 新疆医科大学医学工程技术学院, 乌鲁木齐 830011

收稿日期: 2017-05-27

  网络出版日期: 2019-06-15

基金资助

国家自然科学基金（No.11671344）

收起

Contraction graph method for the interval edge-colorings of graphs

Expand
  • 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 date: 2017-05-27

  Online published: 2019-06-15

Fold

摘要

图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的双圈图类.

关键词： 区间边着色; 收缩图; 下界; 双圈图

本文引用格式

陶艳亮, 黄琼湘, 陈琳 . 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019 , 23(2) : 31 -43 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.003

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

参考文献

[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.
Options
文章导航

/

〈 〉