Раскраска ребер списка

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

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

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

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

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

Самая известная открытая проблема о списочной раскраске рёбер — это, вероятно, гипотеза о списочной раскраске .

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

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

• Галвин, Фред (1995), «Списочный хроматический индекс двудольного мультиграфа», Журнал комбинаторной теории , Серия 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), «Асимптотика списочного хроматического индекса для мультиграфов», Случайные структуры и алгоритмы , 17 (2): 117–156, doi :10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9