Раскраска края списка

В математике раскраска ребер списка — это тип раскраски графа , который сочетает в себе раскраску списка и раскраску ребер . Пример задачи раскраски ребер списка состоит из графа вместе со списком разрешенных цветов для каждого ребра. Раскраска ребер списка — это выбор цвета для каждого ребра из его списка разрешенных цветов; раскраска правильная, если никакие два соседних ребра не окрашены в один и тот же цвет.

Граф G является k -выбираемым ребер , если каждый экземпляр раскраски ребер списка, который имеет G в качестве базового графа и который предоставляет по крайней мере k разрешенных цветов для каждого ребра G , имеет правильную раскраску. Возможность выбора ребра или раскрашиваемость ребра списка , хроматический номер ребра списка или хроматический индекс списка , ch′( G ) графа G является наименьшим числом k таким, что G является k -выбираемым ребром. Предполагается, что он всегда равен хроматическому показателю .

Характеристики

Некоторые свойства ch′( G ):

1. ch′( G ) < 2 χ′( G ).
2. ch′(Kn _{, n )} = n . Это гипотеза Диница , доказанная Галвином (1995) .
3. ch′( G ) < (1 + o(1))χ′( G ), т.е. хроматический индекс списка и хроматический индекс асимптотически согласуются ( Kahn 2000 ).

Здесь χ′( G ) — хроматический индекс группы G ; Kn _{, n —} полный двудольный граф с равными долями .

Гипотеза о раскраске списка

Вероятно, самой известной открытой проблемой раскраски ребер списка является гипотеза об окраске списков .

ch′( G ) = χ′( G ).

Эта гипотеза имеет нечеткое происхождение; Jensen & Toft (1995) делают обзор его истории. Гипотеза Диница, доказанная Галвином (1995) , является частным случаем гипотезы о раскраске списков для полных двудольных графов K _{n , n} .

использованная литература

• Гэлвин, Фред (1995), «Списковый хроматический индекс двудольного мультиграфа», Journal of Combinatorial Theory , Series B, 63 : 153–158, doi : 10.1006/jctb.1995.1011.
• Дженсен, Томми Р.; Тофт, Бьярн (1995), «12.20 List-Edge-Chromatic Numbers», проблемы раскраски графов , Нью-Йорк: Wiley-Interscience, стр. 201–202, ISBN 0-471-02865-7.
• Кан, Джефф (2000), «Асимптотика хроматического индекса списка для мультиграфов», Random Structures & Algorithms , 17 (2): 117–156, doi : 10.1002/1098-2418 (200009) 17: 2 <117 :: AID -RSA3>3.0.CO;2-9