A note on Reed's conjecture
rabern, landon
Original · EN
In reed97, Reed conjectures that the inequality χ(G) ≤ 1/2 (ω(G) + Δ(G) + 1) holds for any graph G. We prove this holds for a graph G if G is disconnected. From this it follows that the conjecture holds for graphs with χ(G) > |G|/2. In addition, the conjecture holds for graphs with Δ(G) ≥ |G| - √|G| + 2α(G) + 1. In particular, Reed's conjecture holds for graphs with Δ(G) ≥ |G| - √|G| + 7. Using these results, we proceed to show that if |G| is an even order counterexample to Reed's conjecture, then G has a 1-factor. Hence, for any even order graph G, if χ(G) > 1/2(ω(G) + Δ(G) + 1) + 1, then G is matching covered.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.