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

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

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

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

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

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

$ch'(G)<2\chi '(G)$
$ch'(K_{n,n})=n$ - гипотеза Диница. Доказательство дано Гальвином^[1]^[2]
$ch'(G)<(1+o(1))\chi '(G)$ - предписанный хроматический индекс асимптотически равен хроматическому индексу ^[3],

где $\chi '(G)$ — есть хроматический индекс графа $G$ , а $K_{n,n}$ — есть полный двудольный граф с равными размерами долей

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

ch'(G)

=

\chi '(G)

.

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

↑ ¹ ² Galvin, 1995.
↑ Дистель, 2002, с. 127.
↑ Kahn, 2000.
↑ Jensen, Toft, 1995.

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.

[_5b702308e81f3b28-1] ¹ ² Galvin, 1995.

[_4bd2ab30ed175d89-2] Дистель, 2002, с. 127.

[_fb3944ef1558e455-3] Kahn, 2000.

[_57a2ddbe277f4b9b-4] Jensen, Toft, 1995.

[1]

[2]

[3]

[4]

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

Свойства

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

Примечания

Литература

Категории