On interval Δ-coloring of bipartite graphs

被引：0
作者：
A. M. Magomedov
机构：
[1] Dagestan State University,
来源：
Automation and Remote Control | 2015年 / 76卷
关键词：
Remote Control; Bipartite Graph; Edge Incident; Graph Coloring; Edge Coloring;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
There exists an important class of problems where the minimal-length scheduling comes to regular coloring of a bipartite graph with the least possible number of colors, and the scheduling without downtimes, to the interval coloring of a bipartite graph. Consideration was given to the problem of interval Δ-coloring of the bipartite multigraph. An example was built of the (6, 3)-biregular graph having no interval Δ-coloring.
引用
收藏
页码：80 / 87
页数：7
相关论文
共 13 条
[1]  
Vizing VG(1964)On Estimation of the Chromatic Class of the p-graph Diskret. Anal. 3 25-30
[2]  
Holyer I(1981)The SIAM J. Comput. 10 718-720
[3]  
Even S(1976)-completeness of Edge-coloring SIAM J. Comput. 5 691-703
[4]  
Itai A(1990)On the Complexity of Timetable and Integral Multi-commodity Flow Problems Metody Diskret. Anal. 50 61-72
[5]  
Shamir A(1998)On Interval Colorability of the Edges of Bipartite Graph Ars Combinat. 50 23-32
[6]  
Sevast’yanov SV(1997)On Interval Colourings of Bi-regular Bipartite Graphs Ars Combin. 47 287-298
[7]  
Hanson D(1999)The Complexity of Consecutive Δ-coloring of Bipartite Graphs: 4 Is Easy, 5 Is Hard Discrete Appl. Math. 94 193-203
[8]  
Loten COM(undefined)On the Deficiency of Bipartite Graphs undefined undefined undefined-undefined
[9]  
Toft B(undefined)undefined undefined undefined undefined-undefined
[10]  
Giaro K(undefined)undefined undefined undefined undefined-undefined
12