УДК 519.17
Теоремы существования и достаточности, связанные с локальными преобразованиями графов для задачи о $k$-раскраске
Д. В. Сироткин1
| Аннотация | В данной работе вводится некоторый класс замен подграфов в графах, причем замены из этого класса сохраняют $k$-раскрашиваемость. Каждое такое локальное преобразование графов определяется некоторым шаблоном – набором разбиений множества на его подмножества. Показывается, что заменяющий подграф существует для любого шаблона, а также приводится оценка на количество его вершин от размера шаблона. Данный результат является основным в работе, для его получения были использованы методы теории графов и комбинаторного анализа. Рассматриваемый в работе класс преобразований может быть полезен при построении полиномиальных сведений для задачи о $k$-раскраске. В частности, вместе с основным результатом работы, он может быть использован при редукции данных для решения задачи о $k$-раскраске. |
|---|---|
| Ключевые слова | задача о $k$-раскраске, локальное преобразование, задача реализации, функция Шеннона |
1Сироткин Дмитрий Валерьевич, лаборант, лаборатория теории и практики систем поддержки принятия решений, ФГАОУ ВО "НИУ ВШЭ" (603155, Россия, г. Нижний Новгород, ул. Большая Печерская, д. 25/12); лаборант, кафедра алгебры, геометрии и дискретной математики ФГАОУ ВО "ННГУ им. Н. И. Лобачевского" (603950, Россия, г. Нижний Новгород, пр. Гагарина, д. 23); ORCID: http://orcid.org/ 0000-0002-2682-9867, dmitriy.v.sirotkin@gmail.com
Цитирование: Сироткин Д. В. Теоремы существования и достаточности, связанные с локальными преобразованиями графов для задачи о $k$-раскраске // Журнал Средневолжского математического общества. 2017. Т. 19, № 2. С. 98–104.
DOI 10.15507/2079-6900.19.201701.098-104
