Non-degenerate colorings in the Brook's Theorem

Details Non-degenerate colorings in the Brook's Theorem Non-degenerate colorings in the Brook's Theorem

2008-12-01

arxiv.org/abs/0812.0372v1

Mathematics

Combinatorics

18 pages, 10 figures

Scientific paper

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 the 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.

Affiliated with

Also associated with

No associations

Rating

Non-degenerate colorings in the Brook's Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Non-degenerate colorings in the Brook's Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-degenerate colorings in the Brook's Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-718345