Предписанная раскраска рёбер

Предписанная раскраска рёбер графа — это вид раскраски графов, в которой комбинируется предписанная раскраска и раскраска ребер.

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

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

Есть гипотеза, что это число всегда равно хроматическому индексу.

Свойства

Некоторые свойства  :

  1. - гипотеза Диница. Доказательство дано Гальвином[1][2]
  2. - предписанный хроматический индекс асимптотически равен хроматическому индексу [3],

где — есть хроматический индекс графа , а — есть полный двудольный граф с равными размерами долей

Гипотеза о предписанной раскраске рёбер

Так называемая гипотеза о предписанной раскраске рёбер:

= .

На данный момент не доказана. История этой гипотезы описана у Дженсена и Тофта[4]. Галвином [1] доказан частный случай для полных двудольных графов Kn,n, называемый гипотезой Диница.

Примечания

Литература

  • Fred Galvin. The list chromatic index of a bipartite multigraph // Journal of Combinatorial Theory. — 1995. Т. 63. С. 153–158. doi:10.1006/jctb.1995.1011..
  • Tommy R. Jensen, Bjarne Toft. 12.20 List-Edge-Chromatic Numbers // Graph coloring problems. — New York: Wiley-Interscience, 1995. — С. 201–202. — ISBN 0-471-02865-7.
  • Jeff Kahn. Asymptotics of the list chromatic index for multigraphs // Random Structures & Algorithms. — 2000. Т. 17, вып. 2. С. 117–156. doi:10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9.
  • Рейнгард Дистель. Глава 5.4 «Предписанная раскраска» // Теория графов. — Новосибирск: Издательство Института математики, 2002. — ISBN 5-86134-101-X.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.