Rödl and Tuza proved that sufficiently large (. k+. 1)-critical graphs cannot be made bipartite by deleting fewer than (k2) edges, and that this is sharp. Chen, Erdos, Gyárfás, and Schelp constructed infinitely many 4-critical graphs obtained from bipartite graphs by adding a matching of size 3 (and called them (B + 3)-graphs). They conjectured that every n-vertex (B + 3)-graph has much more than 5. n/3 edges, presented (B + 3)-graphs with 2. n - 3 edges, and suggested that perhaps 2. n is the asymptotically best lower bound. We prove that indeed every (B + 3)-graph has at least 2. n - 3 edges.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics