Skip to content

Erdős problem 74

Start work

Let 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?

Nothing has been recorded here yet.

How far the record reaches3 of 6 stages
  1. Sourceerdos-problems
  2. StatementRetained
  3. Formal4 retained
  4. ResolutionNone filed
  5. WorkNone recorded
  6. DecisionNone here
  7. The questionNot reached
What this record is missingResolution

No source retained here records an outcome for this question.

Its collection still marks it open.

Open the source record
Where the source files it280 share a topic
Graph Theory275Chromatic Number61Cycles22
None carries a Standing. Browse the topic.
Start workOpen sources