Системы пар $q$-удаленных представителей и раскраски графов

В работе доказывается NP-полнота серии задач о раскрасках графов, связанных с задачей назначения радиочастот. Для этого вводятся в рассмотрение задачи о системах $q$-удаленных представителей (родственные задаче о трансверсали семейства множеств, но, в отличие от неё, NP-полные при $q\ge2$), оказавшиеся удобными для доказательств NP-полноты задач о раскрасках. Библ. – 11 назв.