Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 111

Statement. If $G$ is a graph let $h_G(n)$ be defined such that any subgraph of $G$ on $n$ vertices can be made bipartite after deleting at most $h_G(n)$ edges.

What is the behaviour of $h_G(n)$ ? Is it true that $h_G(n)/n\to \infty$ for every graph $G$ with chromatic number $\aleph_1$ ?

Status. Open.

Source. erdosproblems.com/111, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #111, https://www.erdosproblems.com/111.

References.

[EHS82] Erdős, P. and Hajnal, A. and Szemerédi, E., On almost bipartite large chromatic graphs. Theory and practice of combinatorics (1982), 117-123.
[Er81] Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (13)

Problem 74 Set Theory and Infinite Combinatorics A slow edge-deletion budget forces three-colorability graph_coloring/erdos_1979_problems_results_graph_theory_combinatorial_analysis Question (p. 154): graphs of chromatic number aleph_1 and the cost of making subgraphs bipartite graph_coloring/erdos_1982_almost_bipartite_large_chromatic_graphs Lemma 2.1: uncountably chromatic graphs have n-vertex subgraphs with independence number at most (1/2 - epsilon)n Remarks on p. 121: a linear edge-deletion lower bound above omega, and Lovász's finite graphs Theorems 3 and 3.A: arbitrarily large chromatic graphs whose n-vertex subgraphs lose few edges to become bipartite or r-colorable set_systems/erdos_1981_combinatorial_problems_which_i_would_most Set Theory and Infinite Combinatorics set_theory/erdos_1987_problems_finite_infinite_graphs Problem 7 (p. 225): almost bipartite graphs of large chromatic number

Graph