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

A. V. Kostochka, B. M. Reiniger

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)89-94
Number of pages6
JournalEuropean Journal of Combinatorics
Volume46
DOIs
StatePublished - May 1 2015

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges'. Together they form a unique fingerprint.

Cite this