Was able to show that the complement of a counterexample to Reed's conjecture has minimal degree at least 6. The proof suggests a general method.
Also, improved the bound on the maximal degree of a counterexample from
<= n - sqrt( n + 7 ), to
<= n - sqrt( n + 10 ).
8 comments:
you're a square root.
good one.
Some constructive criticism:
Proving constant improvements in a (1-o(1))n upper bound on the maximum degree of a counterexample isn't going to get you anywhere with this conjecture. Attacking this problem head-on for general graphs is an impossibly hard approach -- if you want to make meaningful progress towards Reed's Conjecture you're better off either working on asymptotic results for general graphs, or proving the conjecture outright for certain classes of graphs.
Classes for which the conjecture has been proven include line graphs, quasi-line graphs, complements of triangle-free graphs (you also did this in one of your papers), and claw-free graphs with independence number at most 3, I think. Claw-free graphs would be a very nice class to prove the conjecture for, particularly as Chudnovsky and Seymour have a complete structural characterization of the class.
Getting claw-free graphs would be, let's say, highly nontrivial, and I personally doubt it could be done properly in under 100 pages.
Agreed. That constant improvement was a coincidental by-product of a new method I was working on to prove connectivity conditions on the class of counterexamples.
The original motivation for the upper bound was Reed's paper where he showed that it held for graphs with \Delta + 1 = n using some simple matching theory. A general upper bound on the chromatic number I had been working on improved on this immediately to
\Delta + 1 >= n - 3. I wanted to see how far I could improve it using the general bound with a little more work. The best I could get was
\Delta + 1 >= n - \sqrt( n + 7 ), and I wrote this up. Then it was surprising to me that \Delta + 1 >= n - \sqrt( n + 10 ) just popped out of another method very easily.
I am currently producing some lower bounds on the connectivity of the complement of a counterexample using probabilistic methods.
I wasn't aware that it had been settled for quasi-line graphs. Who did this?
Where did you go Andrew?
The proof for quasi-line graphs can be proved using a similar induction to that used in Chudnovsky and Ovetsky's "coloring quasi-line graphs", which extends Shannon's Theorem (chi \leq 3omega/2) from line graphs to quasi-line graphs using line graphs as the basis of induction. A really nice method but I can't claim to have come up with it. I'm still working on the paper though. It's a bit of a mess because I'm trying to turn it from an inductive proof into a polytime algorithm, which can be a real pain in spite of its obviousness.
Yes, you can definitely prove the proof like that.
That's sweet that you have proved it for quasi-line graphs -- i'm interested to see the paper.
Is there anything else that you know about counterexamples to this conjecture?
Post a Comment