Coloring and The Lonely Graph

Details Coloring and The Lonely Graph Coloring and The Lonely Graph

2007-07-07

arxiv.org/abs/0707.1069v2

Mathematics

Combinatorics

Scientific paper

We improve upper bounds on the chromatic number proven independently in \cite{reedNote} and \cite{ingo}. Our main lemma gives a sufficient condition for two paths in graph to be completely joined. Using this, we prove that if a graph has an optimal coloring with more than $\frac{\omega}{2}$ singleton color classes, then it satisfies $\chi \leq \frac{\omega + \Delta + 1}{2}$. It follows that a graph satisfying $n - \Delta < \alpha + \frac{\omega - 1}{2}$ must also satisfy $\chi \leq \frac{\omega + \Delta + 1}{2}$, improving the bounds in \cite{reedNote} and \cite{ingo}. We then give a simple argument showing that if a graph satisfies $\chi > \frac{n + 3 - \alpha}{2}$, then it also satisfies $\chi(G) \leq \left\lceil\frac{\omega(G) + \Delta(G) + 1}{2}\right\rceil$. From this it follows that a graph satisfying $n - \Delta < \alpha + \omega$ also satisfies $\chi(G) \leq \left\lceil\frac{\omega(G) + \Delta(G) + 1}{2}\right\rceil$ improving the bounds in \cite{reedNote} and \cite{ingo} even further at the cost of a ceiling. In the next sections, we generalize our main lemma to constrained colorings (e.g. r-bounded colorings). We present a generalization of Reed's conjecture to r-bounded colorings and prove the conjecture for graphs with maximal degree close to their order. Finally, we outline some applications (in \cite{BorodinKostochka} and \cite{ColoringWithDoublyCriticalEdge}) of the theory presented here to the Borodin-Kostochka conjecture and coloring graphs containing a doubly critical edge.

Affiliated with

Also associated with

No associations

Rating

Coloring and The Lonely Graph 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 Coloring and The Lonely Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coloring and The Lonely Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-702269