Условие:
В связном графе G каждый блок имеет максимальную степень не более 10. Докажите, что хроматическое число графа меньше либо равно 11.
Решение:
Обозначим через
множество всех порожденных подграфов графа G, а через (G) минимальную из степеней вершин графа G.
Лемма.
Для любого графа G верна оценка его хроматического числа:
Доказательство.
Утверждени...