An improvement on Brooks' Theorem

Details An improvement on Brooks' Theorem An improvement on Brooks' Theorem

2011-02-04

arxiv.org/abs/1102.1021v2

Mathematics

Combinatorics

Scientific paper

We prove that $\chi(G) \leq \max {\omega(G), \Delta_2(G), (5/6)(\Delta(G) + 1)}$ for every graph $G$ with $\Delta(G) \geq 3$. Here $\Delta_2$ is the parameter introduced by Stacho that gives the largest degree that a vertex $v$ can have subject to the condition that $v$ is adjacent to a vertex whose degree is at least as large as its own. This upper bound generalizes both Brooks' Theorem and the Ore-degree version of Brooks' Theorem.

Affiliated with

Also associated with

No associations

Rating

An improvement on Brooks' 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 An improvement on Brooks' Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An improvement on Brooks' Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-52347