Spencer, Joel

Odd-cycle transversal in triangle-free graphs ★★

Conjecture If $G$ is a simple triangle-free graph, then there is a set of at most $n^2/25$ edges whose deletion destroys every odd cycle.

Keywords:

Posted by fhavet
updated March 6th, 2013