###
Steklov Institute of Mathematics at St.Petersburg

#
PREPRINT 11/2007

N. V. Gravin ##
NON-DEGENERATE COLORINGS IN THE BROOK'S THEOREM

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)]

Back to all preprints

Back to the Steklov
Institute of Mathematics at St.Petersburg