Bipartization costs of finite subgraphs of uncountably chromatic graphs
Follow the latest progress by email.
If a graph has uncountable chromatic number, must its worst n-vertex bipartization cost grow faster than linearly in n? Bipartization cost is the fewest edges one must delete to make the finite subgraph bipartite.
Why it matters and what counts as progress
Why it matters: The question links infinite chromatic complexity to unavoidable finite obstructions to bipartiteness.
What counts as progress: Divergence of h_G(n)/n along the whole sequence for every graph not countably colorable, or a counterexample; an unbounded subsequence is a weaker result.
How the problem developed
- 1981 · Open problem [1]
Paul Erdős Asked whether finite subgraphs of uncountably chromatic graphs can require omission of more than a constant multiple of their edges to become bipartite.
- 1985 · Partial result [2]
Paul Erdős and András Hajnal Defined the induced-subgraph edge-deletion cost and proved a quadratic upper bound together with examples for which the cost is not O(n).
- 19 Oct 2026 · Reported claim [3]
PlasmaAI project Reported that h_G(n)/n→∞ for every graph G that is not countably colorable.
AI contribution
Erdős Problem 111: bipartizing finite subgraphs of uncountably chromatic graphs
If a graph is not countably colorable, h_G(n)/n tends to infinity, where h_G(n) is the largest minimum number of edge deletions needed to make an n-vertex subgraph bipartite. Equivalently, a uniform linear deletion bound on all finite subgraphs forces countable colorability. The limit holds for the whole sequence, for graphs of any uncountable chromatic cardinality.
Sources
- Erdős, On the combinatorial problems which I would most like to see solved
- Erdős and Hajnal, Chromatic number of finite and infinite graphs and hypergraphs
- Plasma AI: proof and scoped result
- Research provenance and statement correspondence
- Exact formal statements
- Palomar: versioned checking record
- Erdős problem 111: statement and prior work
Website timeline
Publication dates and editorial changes.
Erdős Problem 111: bipartizing finite subgraphs of uncountably chromatic graphs