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

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

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

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

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

Свойства

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

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

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

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

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

$ch'(G)$ = $\chi '(G)$.

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