Non-degenerate colorings in the Brook's Theorem

Nikolay Gravin

Let $c\ge 2$ and $p\ge c$ be two integers. We will call a proper coloring of the graph $G$ a \textit{$(c,p)$-nondegenerate}, if for any vertex of $G$ with degree at least $p$ the…