zbMATH — the first resource for mathematics

The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges. (English) Zbl 1307.05071
Summary: V. Rödl and Z. Tuza [J. Comb. Theory, Ser. B 38, 204–213 (1985; Zbl 0566.05030)] proved that sufficiently large \((k + 1)\)-critical graphs cannot be made bipartite by deleting fewer than \(k \choose 2\) edges, and that this is sharp. G. Chen et al. [Graphs Comb. 13, No. 2, 139–146 (1997; Zbl 0881.05044)] 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.

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 2, 125-134, (1992) · Zbl 0756.05049
[2] Chen, G.; Erdős, P.; Gyárfás, A.; Schelp, R. H., A class of edge critical 4-chromatic graphs, Graphs Combin., 13, 2, 139-146, (1997) · Zbl 0881.05044
[3] Gyárfás, A., Problems and memories · Zbl 1040.52008
[4] Hakimi, S. L., On the degrees of the vertices of a directed graph, J. Franklin Inst., 279, 290-308, (1965) · Zbl 0173.26404
[5] Kostochka, A.; Yancey, M., Ore’s conjecture for \(k = 4\) and grötzsch theorem, Combinatorica, 34, 323-329, (2014) · Zbl 1349.05111
[6] Kostochka, A.; Yancey, M., Ore’s conjecture on color-critical graphs is almost true, J. Combin. Theory Ser. B, 109, 73-101, (2014) · Zbl 1301.05127
[7] Rödl, V.; Tuza, Z., On color critical graphs, J. Combin. Theory Ser. B, 38, 3, 204-213, (1985) · Zbl 0566.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.