Теоремы существования и достаточности, связанные с локальными преобразованиями графов для задачи о $k$-раскраске

В данной работе вводится некоторый класс замен подграфов в графах, причем замены из этого класса сохраняют $k$-раскрашиваемость. Каждое такое локальное преобразование графов определяется некоторым шаблоном – набором разбиений множества на его подмножества. Показывается, что заменяющий подграф существует для любого шаблона, а также приводится оценка на количество его вершин в зависимости от размера шаблона. Данный результат является основным в работе, для его получения были использованы методы теории графов и комбинаторного анализа. Рассматриваемый в работе класс преобразований может быть полезен при построении полиномиальных сведений для задачи о $k$-раскраске. В частности, вместе с основным результатом работы, он может быть использован при редукции данных для решения задачи о $k$-раскраске.