I‐Colorings, I‐Phasings, and I‐Intersection assignments for graphs, and their applications

This paper studies set assignments on graphs, functions assigning a set S(x) to each vertex x of a graph, and specifically set assignments where each set is a real interval, perhaps of specified minimum length. Such set assignments arise in applied problems dealing with fleet maintenance, mobile radio frequency assignment, task assignment, traffic phasing, banquet preparation, and computer storage optimization. These problems are briefly discussed. They are translated into problems of finding a set coloring [a set assignment in which an edge between x and y implies that S(x) and S(y) are disjoint], a set phasing [a set coloring of the complementary graph], or a set intersection assignment. The paper presents methods for finding set colorings, phasings, and intersection assignments in which the measure of the union of the intervals S(x) is minimized or in which the sum of the lengths of the S(x) is maximized.