Предписанная раскраска рёбер графа — это вид раскраски графов, в которой комбинируется предписанная раскраска и раскраска ребер.
Предписанная раскраска — это вид раскраски графов, в которой каждая вершина может принимать ограниченное множество допустимых цветов. Раскраска ребер — назначение «цветов» рёбрам графа таким образом, что смежные ребра имеют разный цвет.
Граф называется — выбираемым (или предписанно — раскашиваемым), если он имеет правильную предписанную раскраску независимо от способа распределения цветов для каждой вершины. Число выбираемости (или предписанная раскрашиваемость, или предписанное хроматическое число) графа — это наименьшее число , такое что является — выбираемым.
Есть гипотеза, что это число всегда равно хроматическому индексу.
Свойства Некоторые свойства :
- . Доказательство дано Гальвином - предписанный хроматический индекс асимптотически равен хроматическому индексу , где — есть хроматический индекс графа , а — есть полный двудольный граф с равными размерами долей
Гипотеза о предписанной раскраске рёбер Так называемая гипотеза о предписанной раскраске рёбер:
= .
На данный момент не доказана. История этой гипотезы описана у Дженсена и Тофта. Галвином доказан частный случай для полных двудольных графов Kn,n, называемый гипотезой Диница.
Примечания
Литература
.
Категория:Раскраска графа