This preprint was accepted October 23, 2007
ABSTRACT:
Let $c\geq 2$ and $p\geq 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$ there are at least $c$
vertices of different colors adjacent to it.
In our work we prove the following result, which generalizes Brook's
Theorem. Let $D\geq 3$ and $G$ be a graph without cliques on $D+1$
vertices and a degree of any vertex in this graph is not greater
than $D$. Then for every integer $c\geq 2$ there is a proper
$(c,p)$-nondegenerate vertex $D$-coloring of $G$, where
$p=(c^3+8c^2+19c+6)(c-1).$
During the primary proof, some interesting corollaries are derived.
[Full text:
(.ps.gz)]