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

A. V. Kostochka; B. M. Reiniger

doi:10.1016/j.ejc.2014.12.002

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

A. V. Kostochka, B. M. Reiniger

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Rödl and Tuza proved that sufficiently large (. k+. 1)-critical graphs cannot be made bipartite by deleting fewer than (^k₂) 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 language	English (US)
Pages (from-to)	89-94
Number of pages	6
Journal	European Journal of Combinatorics
Volume	46
DOIs	https://doi.org/10.1016/j.ejc.2014.12.002
State	Published - May 1 2015

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2014.12.002

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

@article{32aa014a571d4d9bb9e99b8f2f60131a,

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

abstract = "R{\"o}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{\'a}rf{\'a}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.",

author = "Kostochka, {A. V.} and Reiniger, {B. M.}",

note = "Funding Information: The authors thank Andr{\'a}s Gy{\'a}rf{\'a}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 . ",

year = "2015",

month = may,

day = "1",

doi = "10.1016/j.ejc.2014.12.002",

language = "English (US)",

volume = "46",

pages = "89--94",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

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 -