Problem 744

Let $k$ be a large fixed constant. Let $f_k(n)$ be the minimal $m$ such that there exists a graph $G$ on $n$ vertices with chromatic number $k$ , such that every proper subgraph has chromatic number $<k$ , and $G$ can be made bipartite by deleting $m$ edges.

Is it true that $f_k(n)\to \infty$ as $n\to \infty$ ? In particular, is it true that $f_4(n) \gg \log n$ ?

Source: erdosproblems.com/744

Graph theory
Chromatic number

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The site labels the problem DISPROVED and credits Rödl and Tuza, who show that $f_k(n)$ is the constant $\binom{k-1}{2}$ for all large $n$ , so it does not tend to infinity.

EHS82: Erdős, P. and Hajnal, A. and Szemerédi, E., On almost bipartite large chromatic graphs. Theory and practice of combinatorics (1982), 117-123.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25-42.
Ga68: T. Gallai, On covering of graphs. Theory of Graphs, Proc. Coll. Tihany, Hungary (1968), 231-236.
RoTu85: Rödl, Vojt\v ech and Tuza, Zsolt, On color critical graphs. J. Combin. Theory Ser. B (1985), 204-213.

Problem 744

Status

Proof claims

Discussion