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 th... View more
  • 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.

  • Similar Research Results (2)
  • Metrics
    No metrics available
Share - Bookmark