WikiDer > Раскраска по краям списка

List edge-coloring

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

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

Свойства

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

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

Здесь χ ′ (г) это хроматический индекс из г; и Kп,п, то полный двудольный граф с равным раздельные наборы.

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

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

ch ′ (г) = χ ′ (г).

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

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

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