A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Preemptive open shop scheduling can be viewed as an edge coloring problem in a bipartite multigraph. In some applications, restrictions of colors (in particular preassignments) are made for some edges. We give characterizations of graphs where some special preassignments can be embedded in a minimum coloring (number of colors = maximum degree). The case of restricted colorings of trees is shown to be solvable in polynomial time.
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
L Auslander, E Feig, et al.
Advances in Applied Mathematics