RUS  ENG
Полная версия
ВИДЕОТЕКА

Вторая конференция Математических центров России. Пленарные доклады
9 ноября 2022 г. 11:00, г. Москва, Ломоносовский корпус МГУ


Концепция инциденторных раскрасок

А. В. Пяткин



Аннотация: Инцидентором в ориентированном графе называется пара из вершины и инцидентной ей дуги; инцидентор удобно трактовать как половину дуги, примыкающую к данной вершине. Требуется раскрасить инциденторы мультиграфа в минимальное число цветов с соблюдением заданных ограничений на цвета смежных (имеющих общую вершину) и сопряженных (имеющих общую дугу) инциденторов. В докладе будет полностью освещена концепция таких раскрасок: история возникновения модели, развитие методов, краткий обзор результатов и остающихся открытыми проблем.


© МИАН, 2024