This question was inspired by a theorem of Babai, that if $G$ is a graph on a well-ordered set with chromatic number $\geq \aleph_0$ there is a subgraph on vertices with order-type $\omega$ with chromatic number $\aleph_0$.

Erdő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. We connect $(x_{\alpha_1},y_{\beta_1})$ and $(x_{\alpha_2},y_{\beta_2})$ if and only if $\alpha_1<\alpha_2$ and $\beta_1<\beta_2$.

A similar construction produces a graph on $\omega_2^2$ with chromatic number $\aleph_2$ such that every smaller subgraph has chromatic number $\leq \aleph_1$.

View the LaTeX source