Невырожденные раскраски графов

Пусть $G$ – простой граф степени $d\geq 3$, не содержащий $K_{d+1}$ – полный подграф (клику) на $d+1$ вершине. Известная теорема Брукса утверждает, что существует правильная раскраска вершин $G$ в $d$ цветов. При этом существует множество обобщений этого результата, одно из которых мы рассмотрим. Для вершинной раскраски $\rho$ обозначим за $m_v(\rho)$ количество разных цветов, представленных в окрестности вершины, а $d_v$ – её степень. Для произвольного набора чисел $\{m_v\}_{v\in V(G)}$ правильная раскраска $\rho$ называется $m_v$-невырожденной, если $m_v(\rho)\geq m_v$ для всех $v \in V(G)$. В докладе мы обсудим следующий результат:
Теорема.
Пусть $G$ – простой граф степени $d$, не содержащий $K_{d+1}$, а $d$ достаточно велико. Пусть $m_v=\frac{d_v}{18}-10\sqrt{d_v \ln{d}}$ для каждой вершины $v$. Тогда существует $m_v$-невырожденная раскраска графа $G$ в $d$ цветов.
Доказательство можно поделить на две части: комбинаторную и вероятностную. В первой мы покажем, как получить из графа степени $d$ граф специального вида, и оценим, как при этом преобразуется $m_v$. Во второй опишем, как устроена случайная частичная раскраска графа и почему с положительной вероятностью она может быть продолжена до интересующей нас.