Графы с цветными ребрами
Корректной раскраской графа в два цвета называется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют двудольными. Заметим, что если такая раскраска существует, и если зафиксировать цвет одной вершины, то все цвета всех достижимых из неё вершин определяются однозначно: пусть цвет этой вершины белый, тогда все её соседи будут иметь черный цвет, все вершины на расстоянии 2 будут иметь снова белый цвет, все вершины на расстоянии 3 снова черный, и так далее. Проверять граф на двудольность и выводить раскраску можно обходом в глубину. На этот раз наш dfs будет принимать параметром цвет, в который нужно покрасить вершину, и он будет рекурсивно запускаться от всех соседей, крася их в противоположный цвет. По окончании работы алгоритма мы либо обнаружим, что граф не двудолен мы когда-то посмотрели на две соседние вершины, которым нужно присвоить один и тот же цвет , либо найдём разбиение вершин графа на две доли.
![[В работе] Конспект лекции по раскраскам](http://www.mochalova.ru/meth_artterapia/graph/urok07_ill015.gif "2.4. Алгоритм минимальной раскраски вершин (ребер) графа g")
В силу его двудольности, это число будет равняться сумме степеней вершин одной из долей. А по лемме о нижней оценки, меньше цветов использовать нельзя. Материал из Викиконспекты.
Вводим понятие списочной раскраски. Демонстрируем различие между обчным и списочным хроматическим числом. Доказываем теоремы Брукса и Визинга. Доказываем теорему Алона об оценки списочного хроматического числа через минимальную степень вершин. Доказываем верхнюю оценку на списочное хроматическое число через обычное.
