Erdős Problem #74 — Let f(n)→ ∞ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on n vertices can be made bipartite by deleting at most f(n) edges?

Question

Let f(n)→ ∞ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on n vertices can be made bipartite by deleting at most f(n) edges?

Erdős Problem #74 — Let $f(n)\to \infty$ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?

Primary source

Additional references

Progress summary

Solutions 0