Coloring and The Lonely Graph

Preprint English OPEN
Rabern, Landon (2007)
  • Subject: Mathematics - Combinatorics | 05C15

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.
  • References (6)

    [1] Landon Rabern. A note on Reed's conjecture, 2006.

    [2] Landon Rabern. On Graph Associations. SIAM J. Discrete Math., 20(2):529-535, 2006.

    [3] Landon Rabern. The Borodin-Kostochka Conjecture For Graphs Containing a Doubly Critical Edge. Submitted to Journal of Combinatorial Theory, 2007.

    [4] Landon Rabern. Coloring Graphs Containing a Doubly Critical Edge. Submitted to Journal of Graph Theory, 2007.

    [5] Bert Randerath and Ingo Schiermeyer. On Reed's conjecture about ω,Δ and χ. Graph Theory in Paris (Series: Trends in Mathematics), Proceedings of a Conference in Memory of Claude Berge, pages 339-346, 2006.

    [6] Bruce Reed. ω, Δ, and χ. J. Graph Theory., 27:177-212, 1997.

  • Metrics
    No metrics available
Share - Bookmark