The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges

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