Problem #1068: Does every graph with chromatic number $\aleph_1$ contain a...

---

Progress

I do not think this was originally a question of Erdős - it appears in [BoPi24] as a 'version of the Erdős-Hajnal problem' (which is [1067]).

I could not in fact find this in the paper of Erdős and Hajnal [ErHa66], however, and hence the first place it appears may in fact be in [BoPi24]. In hindsight this should not have been included as a separate problem, but this has been discovered too late, and so we must leave it here.

We say a graph is infinitely (vertex) connected if any two vertices are connected by infinitely many pairwise vertex-disjoint paths.

Soukup [So15] constructed a graph with uncountable chromatic number in which every uncountable set is finitely vertex-connected. A simpler construction was given by Bowler and Pitz [BoPi24].

See also [1067].