A generalization of interval edge-colorings of graphs

被引：3
|
作者：
Petrosyan, P. A. [1 ,2 ]
Arakelyan, H. Z. [1 ]
Baghdasaryan, V. M. [1 ]
机构：
[1] Yerevan State Univ, Dept Informat & Appl Math, Yerevan 0025, Armenia
[2] Natl Acad Sci, Inst Informat & Automat Problems, Yerevan 0014, Armenia
来源：
DISCRETE APPLIED MATHEMATICS | 2010年 / 158卷 / 16期
关键词：
Edge-coloring; Interval coloring; Chromatic index; Bipartite graph; ONE TIME OPERATIONS; BIPARTITE GRAPHS; SPORTS SCHEDULES;
D O I：
10.1016/j.dam.2010.06.012
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
An edge-coloring of a graph G with colors 1, 2, ..., t is called an interval (t, 1)-coloring if at least one edge of G is colored by i, i = 1, 2,... t, and the colors of edges incident to each vertex of G are distinct and form an interval of integers with no more than one gap. In this paper we investigate some properties of interval (t, 1)-colorings. We also determine exact values of the least and the greatest possible number of colors in such colorings for some families of graphs. (C) 2010 Elsevier B.V All rights reserved.
引用
收藏
页码：1827 / 1837
页数：11
相关论文
共 50 条
  • [1] Interval edge-colorings of complete graphs
    Khachatrian, H. H.
    Petrosyan, P. A.
    DISCRETE MATHEMATICS, 2016, 339 (09) : 2249 - 2262
  • [2] On Interval Edge-Colorings of Bipartite Graphs
    Petrosyan, Petros
    Khachatrian, Hrant
    Mamikonyan, Tigran
    TENTH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INFORMATION TECHNOLOGIES REVISED SELECTED PAPERS CSIT-2015, 2015, : 71 - 76
  • [3] INVESTIGATION ON INTERVAL EDGE-COLORINGS OF GRAPHS
    ASRATIAN, AS
    KAMALIAN, RR
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) : 34 - 43
  • [4] Interval cyclic edge-colorings of graphs
    Petrosyan, P. A.
    Mkhitaryan, S. T.
    DISCRETE MATHEMATICS, 2016, 339 (07) : 1848 - 1860
  • [5] Interval edge-colorings of composition of graphs
    Tepanyan, H. H.
    Petrosyan, P. A.
    DISCRETE APPLIED MATHEMATICS, 2017, 217 : 368 - 374
  • [6] On Interval Edge-Colorings of Outerplanar Graphs
    Petrosyan, Petros A.
    ARS COMBINATORIA, 2017, 132 : 127 - 135
  • [7] On Interval Edge-colorings of Complete Tripartite Graphs
    Grzesik, Andrzej
    Khachatrian, Hrant
    2013 COMPUTER SCIENCE AND INFORMATION TECHNOLOGIES (CSIT), 2013,
  • [8] EDGE-COLORINGS OF GRAPHS
    ANDERSEN, LD
    MATHEMATICA SCANDINAVICA, 1977, 40 (02) : 161 - 175
  • [9] INTERVAL EDGE-COLORINGS OF CARTESIAN PRODUCTS OF GRAPHS I
    Petrosyan, Petros A.
    Khachatrian, Hrant H.
    Tananyan, Hovhannes G.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (03) : 613 - 632
  • [10] MAXIMAL EDGE-COLORINGS OF GRAPHS
    Babinski, S.
    Grzesik, A.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (03): : 403 - 407
12345