A note on Reed's conjecture
| dc.creator | rabern, landon | |
| dc.date | 2006-04-24 | |
| dc.date.accessioned | 2026-07-07T07:11:11Z | |
| dc.date.available | 2026-07-07T07:11:11Z | |
| dc.description | In \cite{reed97}, Reed conjectures that the inequality $χ(G) \leq \left \lceil \textstyle {1/2} (ω(G) + Δ(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 $χ(G) > \left \lceil \frac{|G|}{2} \right \rceil$. In addition, the conjecture holds for graphs with $Δ(G) \geq |G| - \sqrt{|G| + 2α(G) + 1}$. In particular, Reed's conjecture holds for graphs with $Δ(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 $χ(G) > \textstyle {1/2}(ω(G) + Δ(G) + 1) + 1$, then $\bar{G}$ is matching covered. | |
| dc.identifier | https://arxiv.org/abs/math/0604499 | |
| dc.identifier | http://arxiv.org/abs/math/0604499 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/111663 | |
| dc.subject | Combinatorics | |
| dc.title | A note on Reed's conjecture | |
| dc.type | text |