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

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

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

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

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

Свойства

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

1. $c{h}^{\prime }(G)<2{\chi }^{\prime }(G)$
2. $c{h}^{\prime }(K_{n,n})=n$ - Шаблон:Не переведено 5. Доказательство дано ГальвиномШаблон:SfnШаблон:Sfn
3. $c{h}^{\prime }(G)<(1+o(1)){\chi }^{\prime }(G)$ - предписанный хроматический индекс асимптотически равен хроматическому индексу Шаблон:Sfn,

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

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

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

$c{h}^{\prime }(G)$ = ${\chi }^{\prime }(G)$.

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

Литература

• Шаблон:Статья.
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга