Paper detail

Coloring and The Lonely Graph

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ω{2}$ singleton color classes, then it satisfies $χ\leq \frac{ω+ Δ+ 1}{2}$. It follows that a graph satisfying $n - Δ< α+ \frac{ω- 1}{2}$ must also satisfy $χ\leq \frac{ω+ Δ+ 1}{2}$, improving the bounds in \cite{reedNote} and \cite{ingo}. We then give a simple argument showing that if a graph satisfies $χ> \frac{n + 3 - α}{2}$, then it also satisfies $χ(G) \leq \left\lceil\frac{ω(G) + Δ(G) + 1}{2}\right\rceil$. From this it follows that a graph satisfying $n - Δ< α+ ω$ also satisfies $χ(G) \leq \left\lceil\frac{ω(G) + Δ(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.