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

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

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

Свойства

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

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

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

списка

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

ч ′ ( грамм ) знак равно χ ′ ( грамм ).

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

Ссылки

• Гэлвин, Фред (1995), «Списочный хроматический индекс двудольного мультиграфа», Журнал комбинаторной теории , серия B, 63 : 153–158, doi : 10.1006/jctb.1995.1011 .
• Дженсен, Томми Р.; Тофт, Бьерн (1995), «12.20 Хроматические числа по краям списка», Проблемы раскраски графов , Нью-Йорк: 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