Systems of pair of $q$-distant representatives and graph colorings

NP-completeness of a number of graph coloring problems connected with the frequency assignment problem is proved. For this purpose we introduce problems concerning systems of pairs of $q$-distant representatives (related to the well known problem about the system of distinct representatives, but being NP-complete for $q\ge2$), which turned out to be convenient for proving NP-completeness of various graph coloring problems.