Permanent problem IDPPL 079
Graph theory
Let f(n)→ ∈fty (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?
Let f(n)→ ∈fty (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?
A solution must appear in a reputable journal, with documentation that Erdős offered the displayed amount. Claims are administered by the Combinatorics Foundation; erdosproblems.com does not pay awards.