Erdős Problem #74 — Nearly bipartite finite subgraphs of infinite-chromatic graphs
Let be a function on the positive integers with , possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on vertices can be made bipartite by deleting at most edges? More explicitly, for a graph with chromatic number , the required condition is that for every finite subgraph ,
Here and are the vertex and edge sets, and is obtained by deleting the edges in . The question as worded does not separately specify a quantifier over choices of . Erdős Problems #74
Background
Erdős, Hajnal, and Szemerédi posed the problem in 1982, asking whether graphs can have infinite chromatic number while every finite subgraph is close to bipartite in this edge-deletion sense. The issue is how slowly the permitted number of deletions can grow with the subgraph’s number of vertices while still allowing unbounded chromatic complexity. Erdős Problems #74
Rödl’s 1982 work is an early connection between near-bipartiteness and large chromatic number: the problem page reports results both for hypergraphs and, for graphs, when the deletion allowance is linear in the number of vertices. Erdős Problems #74 Rödl (1982)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.