Erdős Problem #919

declared status 'open'. Formalized: no. Is there a graph $G$ with vertex set $\omega_2^2$ and chromatic number $\aleph_2$ such that every subgraph whose vertices have a lesser type has chromatic number $\leq \aleph_0$? What if instead we ask for $G$ to have chromatic number $\aleph_1$? Current best: Erd\H{o}s and Hajnal showed this does not generalise to higher cardinals - they (see [Er69b]) constructed a set on $\omega_1^2$ with chromatic number $\aleph_1$ such that every strictly smaller subgraph has chromatic number $\leq \aleph_0$ as follows: the vertices of $G$ are the pairs $(x_\alpha,y_\beta)$ for $1\leq \alpha,\beta <\omega_1$, ordered lexicographically. Prize: no. Tags: chromatic number, graph theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.