Инъективная $L(2,1)$-раскраска как оптимизационная задача на множестве перестановок вершин графа: доминантно-пороговые графы

Рассматривается задача инъективной $\lambda$-раскраски, которая почти для всех графов совпадает с исходной задачей. Мы приводим новую интерпретацию задачи инъективной раскраски как оптимизационной задачи на множестве перестановок вершин графа. Используя декомпозицию доминантно-порогового графа (нормальную форму), разработан алгоритм решающий обе задачи обычной и инъективной раскрасок в классе доминантно-пороговых графов за время $O(n+m)$. Применительно к пороговым графам этот алгоритм находит решение за то же время $O(n)$.