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

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