Geodesic
Systems of pair of $q$-distant representatives and graph colorings
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VII, Tome 293 (2002), pp. 5-25 
P. A. Golovach. Systems of pair of $q$-distant representatives and graph colorings. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VII, Tome 293 (2002), pp. 5-25. http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a0/
@article{ZNSL_2002_293_a0,
     author = {P. A. Golovach},
     title = {Systems of pair of $q$-distant representatives and graph colorings},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {5--25},
     year = {2002},
     volume = {293},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a0/}
}
TY  - JOUR
AU  - P. A. Golovach
TI  - Systems of pair of $q$-distant representatives and graph colorings
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2002
SP  - 5
EP  - 25
VL  - 293
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a0/
LA  - ru
ID  - ZNSL_2002_293_a0
ER  - 
%0 Journal Article
%A P. A. Golovach
%T Systems of pair of $q$-distant representatives and graph colorings
%J Zapiski Nauchnykh Seminarov POMI
%D 2002
%P 5-25
%V 293
%U http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a0/
%G ru
%F ZNSL_2002_293_a0

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

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.