Problem 111

Statement

If $G$ is a graph let $h_G(n)$ be defined such that any subgraph of $G$ on $n$ vertices can be made bipartite after deleting at most $h_G(n)$ edges.

What is the behaviour of $h_G(n)$ ? Is it true that $h_G(n)/n\to \infty$ for every graph $G$ with chromatic number $\aleph_1$ ?

Source: erdosproblems.com/111

Graph theory
Chromatic number
Set theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Solved: an accepted full claim answers the limit question, and the open-ended first question does not block the standing. Bloom's catalog labeled the problem open. Plasma AI's full claim answers the limit question yes; it is accepted on this corpus's rebuild, Comparator check and kernel replay of its Lean formalization and a graded review of its statements, and Current assessment gives its review.

Problem 111

Statement

Status

Proof claims

Discussion