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

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

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

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

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

СвойстваПравить

Некоторые свойства $c{h}^{\prime }(G)$$ch'(G)$  :

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

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

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

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

$c{h}^{\prime }(G)$$ch'(G)$  = ${\mathrm{\chi <!--\; \chi \; -->}}^{\prime }(G)$$\chi '(G)$ .

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