publication . Preprint . 2007

Coloring and The Lonely Graph

Name: Coloring and The Lonely Graph
Creator: Rabern, Landon

Rabern, Landon;

Open Access English

Published: 07 Jul 2007

Summary
references
6

Abstract

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}...

Subjects

free text keywords: Mathematics - Combinatorics, 05C15

Download from

arXiv.org e-Print Archive

Preprint . 2007

Provider: arXiv.org e-Print Archive

[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. [OpenAIRE]

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

[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. [OpenAIRE]

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

Any information missing or wrong?Report an Issue