The NP-completeness of a number of graph coloring problems related to the frequency assignment problem is proved. For this purpose, we introduce problems concerning systems of pairs of q-distant representatives (which are related to the well-known problem about the system of distinct representatives, but are NP-complete for q ≥ 2), which turned out to be convenient for proving the NP-completeness of various graph coloring problems. Bibliography: 11 titles.
展开▼
