Идентификатор конференции: 912 824 7824
Код доступа: 31415926
В. Н. Потапов (Новосибирск)
Экстремальные комбинаторные конфигурации и совершенные раскраски графов.
Аннотация
Известно множество случаев, когда точное решение некоторой экстремальной комбинаторной задачи соответствует совершенной раскраске графа или гиперграфа. Предполагается рассмотреть несколько таких задач, связанных с независимыми множествами и разрезами в графах, а также продемонстрировать на простом примере метод доказательства неравенств, приводящих в случае достижения равенства к совершенной раскраске.
Доклад основан на препринте On extremal properties of perfect 2-colorings https://arxiv.org/abs/2204.03308.