← All problems

Erdős Problem #74 — Nearly bipartite finite subgraphs of infinite-chromatic graphs

1 year old · traced to

Let ff be a function on the positive integers with f(n)→∞f(n)\to\infty, possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on nn vertices can be made bipartite by deleting at most f(n)f(n) edges? More explicitly, for a graph GG with chromatic number χ(G)=∞\chi(G)=\infty, the required condition is that for every finite subgraph H⊆GH\subseteq G,

∃DH⊆E(H)∣DH∣≤f(∣V(H)∣),H−DH is bipartite.\exists D_H\subseteq E(H)\quad |D_H|\leq f(|V(H)|),\qquad H-D_H\text{ is bipartite}.

Here V(H)V(H) and E(H)E(H) are the vertex and edge sets, and H−DHH-D_H is obtained by deleting the edges in DHD_H. The question as worded does not separately specify a quantifier over choices of ff. 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

Progress summary

Never refreshed

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.