Участник:Kirillskor/Задача chromatic-numbers-for-graph-with-degree — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 15: Строка 15:
 
Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей.
 
Начнем красить с последней вершины: на каждом шаге у текущей вершины v есть не более d-1 покрашенных соседей, т.к. ее степень \leq d, а ее предок не покрашен, либо это вершина u и у нее по определению < d соседей.
  
 
+
\vspace{3mm}
  
 
Пусть теперь все вершины в графе имеют степень d.
 
Пусть теперь все вершины в графе имеют степень d.
  
 
Рассмотрим вершины b, c смежные с a.
 
Рассмотрим вершины b, c смежные с a.
 
 
Если удаление b и c делает граф несвязным - то его можно покрасить в d цветов, т.к. в каждой связной компоненте есть вершина степени < d.
 
Если удаление b и c делает граф несвязным - то его можно покрасить в d цветов, т.к. в каждой связной компоненте есть вершина степени < d.
  

Версия 20:23, 9 декабря 2017