Problem 75

Is there a graph of chromatic number $\aleph_1$ with $\aleph_1$ vertices such that for all $\epsilon>0$ if $n$ is sufficiently large and $H$ is a subgraph on $n$ vertices then $H$ contains an independent set of size $>n^{1-\epsilon}$ ?

What about an independent set of size $\gg n$ ?

Source: erdosproblems.com/75

Graph theory
Chromatic number

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label. The first question has a pending partial claim, the Specker graph answers the n^(1-epsilon) question.

Problem 75

Status

Proof claims

Discussion