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.
login/create account
Drupal
CSI of Charles University
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.