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
相关论文
共 34 条
  • [1] ANDERSEN LD, 1983, P LOND MATH SOC, V47, P507
  • [2] [Anonymous], 1969, Comb. Math. Appl
  • [3] Asratian A. S., 1998, Cambridge Tracts in Mathematics
  • [4] Asratian A.S., 1987, Appl. Math., V5, P25
  • [5] On interval edge colorings of (α, β)-biregular bipartite graphs
    Asratian, Armen S.
    Casselgren, C. J.
    [J]. DISCRETE MATHEMATICS, 2007, 307 (15) : 1951 - 1956
  • [6] INVESTIGATION ON INTERVAL EDGE-COLORINGS OF GRAPHS
    ASRATIAN, AS
    KAMALIAN, RR
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) : 34 - 43
  • [7] ASRATIAN AS, 1978, VESTNIK MOSKOV U SER, V15, P74
  • [8] Brelaz D., 1977, Zeitschrift fur Operations Research, Serie A (Theorie), V21, P65, DOI 10.1007/BF01918457
  • [9] PREPARATION OF EXAMINATION TIME-TABLES USING SMALL-STORE COMPUTER
    COLE, AJ
    [J]. COMPUTER JOURNAL, 1964, 7 (02) : 117 - &
  • [10] Construction of sports schedules with multiple venues
    de Werra, D
    Ekim, T
    Raess, C
    [J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (01) : 47 - 58
1234