Yesterday i proved that the a counterexample to Reed's conjecture has two connected complement. The proof is written in my notebook, will TeX it when i get a chance.
This followed immediately from the following improvement of the graph associations theorem.
If I_1, ..., I_m are disjoint independent sets in G, then at least one of the following holds
1) \chi(G) \leq \frac{1}{2} (\omega(G) + \Delta(G) + 2)
2) \chi(G) \leq \frac{1}{2}(\omega(G) + n - \sum_{j=1}^m |I_j| + 2m - 2)
So, in other words, the graph associations bound can be improved by 1/2 for counterexamples to Reed's conjecture.
No comments:
Post a Comment