Об интервальной $(1,1)$-раскраске инциденторов интервально раскрашиваемых графов

Граф назвается интервально раскрашиваемым, если существует такая правильная раскраска его рёбер, что для каждой вершины набор цветов, использованных для раскраски рёбер, примыкающих к ней, образует интервал. Подразбиением графа называется граф, полученный заменой каждого ребра путём длины 2. П. Петросян и Х. Хачатрян выдвинули гипотезу, что подразбиение любого интервально раскрашиваемого графа интервально раскрашиваемо. В настоящей работе приводится доказательство этой гипотезы. Библиогр. 19.