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

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

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

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

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

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

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

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

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

${\displaystyle ch'(G)}$ = ${\displaystyle \chi '(G)}$.

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