TY - JOUR

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

AU - Kostochka, A. V.

AU - Reiniger, B. M.

N1 - Funding Information:
The authors thank András Gyárfás for attracting attention to the problem and helpful discussions; and the anonymous referee for helpful comments, in particular, for pointing out the second of the graphs in Fig. 5 . Research of the first author is supported in part by National Science Foundation grant DMS-1266016 and by grants 12-01-00631 and 12-01-00448 of the Russian Foundation for Basic Research . Research of the second author is supported in part by National Science Foundation grant DMS-0838434 .

PY - 2015/5/1

Y1 - 2015/5/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84920896690&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84920896690&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2014.12.002

DO - 10.1016/j.ejc.2014.12.002

M3 - Article

AN - SCOPUS:84920896690

VL - 46

SP - 89

EP - 94

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

ER -