Предписанная раскраска рёбер (Hjy;hnvguugx jgvtjgvtg j~Qyj)

Перейти к навигации Перейти к поиску

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

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

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

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

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

  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.