Coloring and The Lonely Graph

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

f r a c o m e g a 2

singleton color classes, then it satisfies

c h i l e q f r a c o m e g a + D e l t a + 1 2

. It follows that a graph satisfying

n - D e l t a < a l p h a + f r a c o m e g a - 1 2

must also satisfy

c h i l e q f r a c o m e g a + D e l t a + 1 2

, improving the bounds in cite{reedNote} and cite{ingo}. We then give a simple argument showing that if a graph satisfies

c h i > f r a c n + 3 - a l p h a 2

, then it also satisfies

c h i (G) l e q l e f t l c e i l f r a c o m e g a (G) + D e l t a (G) + 1 2 i g h t c e i l

. From this it follows that a graph satisfying

n - D e l t a < a l p h a + o m e g a

also satisfies

c h i (G) l e q l e f t l c e i l f r a c o m e g a (G) + D e l t a (G) + 1 2 i g h t c e i l

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.

This page was built for publication: Coloring and The Lonely Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6206138)