CHROMATIC SCHEDULING AND FREQUENCY ASSIGNMENT

Some extensions of classical coloring models are developed; these cons ist in assigning to each node a set of consecutive colors; furthermore for each oriented arc (i, j) in a graph a set T(ij) of consecutive in tegers is given. It is required to find an assignment of colors to the nodes such that for each arc (i,j) the first colors f(i), f(j) given to nodes i and j satisfy f(j) - f(i) is-not-an-element-of T(ij). This model can be used for assigning frequencies to a collection of station s as well as for chromatic scheduling problems. Simple upper bounds on the generalized chromatic number are derived. Computational results a re reported for some randomly generated problems.