Interval edge-coloring: A model of curriculum scheduling. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Shao, Zehui; Li, Zepeng; Wang, Bo; Wang, Shaohui; Zhang, Xiujun
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 725
• Page End: 729
• Publication Date: 2020-09-01
• Subjects: Interval coloring -- complete tripartite graphs -- complete multipartite graphs
• DOI: 10.1016/j.akcej.2019.09.003
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: Considering the appointments that teachers plan to teach some courses for specific classes, the problem is to schedule the curriculum such that the time for each teacher is consecutive. In this work, we propose an integer linear programming model to solve consecutive interval edge-coloring of a graph. By using the proposed method, we give the interval edge colorability of some small complete multipartite graphs. Moreover, we find some new classes of complete multipartite graphs that have interval edge-colorings and disprove a conjecture proposed by Grzesik and Khachatrian (2014).