Independent sets in finite subgraphs of infinite-chromatic graphs
Follow the latest progress by email.
Can an infinite-chromatic graph look almost bipartite on every finite subgraph, in the sense of containing an independent set of size at least m/2−f(m) for a prescribed unbounded error f? A stronger target bounds finite-subgraph odd-cycle-transversal numbers.
Why it matters and what counts as progress
Why it matters: Arbitrarily small unbounded local errors test how little finite-subgraph evidence can coexist with infinite global chromatic number.
What counts as progress: Construct infinite-chromatic graphs for arbitrarily slow unbounded error profiles or prove a local obstruction forcing finite chromatic number.
How the problem developed
- 3 May 2026 · Reported solution [1]
Przemek Chojecki and GPT-5.5 Pro Their note reports that every m-vertex finite subgraph of an infinite-chromatic graph has an independent set of size at least m/2−f(m), for every nonnegative f tending to infinity.
AI contribution
Local Odd-Cycle Transversals in Generalized Mycielski Graphs and an Erdős Problem on Almost-Half Independent Sets
An infinite-chromatic graph has the property that, for every nonnegative function f(m) tending to infinity, every m-vertex finite subgraph contains an independent set of size at least m/2−f(m). A stronger construction bounds local odd-cycle-transversal number by any prescribed unbounded integer profile.
Sources
Website timeline
Publication dates and editorial changes.