Name: Coloring and The Lonely Graph
Creator: Rabern, Landon
Keywords: Mathematics - Combinatorics, 05C15

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 (4)

publication On the tree cover number and the positive semidefinite maximum nullity of a graph (2018)	80%
publication Optimal pebbling number of the square grid (2018)	80%
publication On graph identification problems and the special case of identifying vertices using paths (2012)	80%
publication Complete graph immersions in dense graphs (2015)	79%

Metrics

Share - Bookmark

Download from
arXiv.org e-Print Archive via arXiv.org e-Print Archive (Preprint, 2007)
Cite this publication