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