A note on Reed's conjecture

Details A note on Reed's conjecture A note on Reed's conjecture

2006-04-24

arxiv.org/abs/math/0604499v1

Mathematics

Combinatorics

Scientific paper

In \cite{reed97}, Reed conjectures that the inequality $\chi (G) \leq \left \lceil \textstyle {1/2} (\omega (G) + \Delta (G) + 1) \right \rceil$ holds for any graph $G$. We prove this holds for a graph $G$ if $\bar{G}$ is disconnected. From this it follows that the conjecture holds for graphs with $\chi(G) > \left \lceil \frac{|G|}{2} \right \rceil$. In addition, the conjecture holds for graphs with $\Delta(G) \geq |G| - \sqrt{|G| + 2\alpha(G) + 1}$. In particular, Reed's conjecture holds for graphs with $\Delta(G) \geq |G| - \sqrt{|G| + 7}$. Using these results, we proceed to show that if $|G|$ is an even order counterexample to Reed's conjecture, then $\bar{G}$ has a 1-factor. Hence, for any even order graph $G$, if $\chi(G) > \textstyle {1/2}(\omega(G) + \Delta(G) + 1) + 1$, then $\bar{G}$ is matching covered.

Affiliated with

Also associated with

No associations

Rating

A note on Reed's conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A note on Reed's conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on Reed's conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583005