Distance graphs and the \(T\)-coloring problem (Q1297406)

By the \(T\)-colouring problem we mean a generalized graph colouring problem which is one of the variants of the channel assignment problem in broadcast networks. The set \(T\) describes which channel distances are ``forbidden'' in order to prevent interference between transmitters. The \(T\)-colouring problem for complete graphs is equivalent to the clique problem for distance graphs. It is shown that (1) the \(T\)-colouring problem for complete graphs is NP-complete in the strong sense and (2) the ordered distance graphs can be recognized in polynomial time using linear programming techniques.