Abstract:
A. S. Asratyan and C. J. Casselgren proved that the problem of the interval edge-coloring of biregular bipartite graph with degrees 6 and 3 respectively («(6,3)-graph») is NP-complete. The article shows that the minimum capacity of vertices $n$ such that (6,3)-graph prevents coloring of the required form equal to 18: any (6,3)-graph with $n<18$ allows interval edge-coloring; for each $n$ not less than 18 (and divided by 3) there is (6,3)-graph with $n$ vertices, for which a coloring impossible. The results are used for constructing an optimal schedules training sessions.
Fulltext:
PDF file (534 kB)