The statement of the

The statement of the conjecture is slightly incorrect. Instead of the +1 at the end, there should simply be a round-up. The conjecture is true for line graphs and quasi-line graphs, graphs with independence number 2, and any graph on I believe 12 vertices.

An outright proof of the result for triangle-free graphs would be very nice. Lovasz' result on splitting graphs is not quite enough in this case.

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options