---

Statement

Remark (3) (Section 4, p. 3). The authors state that a version of the Erdős-Hajnal problem remains open, and pose it as a question (quoted): "Does every uncountably chromatic graph have a countably infinite, infinitely connected subgraph?"

The question asks for a subgraph that is countably infinite, which excludes the trivial one-vertex case, and concerns every graph of uncountable chromatic number, not only those of chromatic number $\aleph_1$. The remark is a statement of an open question, not a result; the note proves nothing toward it.

Source. Nathan Bowler and Max Pitz, A note on uncountably chromatic graphs, arXiv:2402.05984v2 (17 May 2024); Electron. J. Combin. 32 (2025), no. 1, Paper No. P1.23: Remark (3) in Section 4, p. 3. Pages are those of arXiv v2, the edition identified on the source card.

Read depth. Claims checked: the remark was read on the printed page.

Context

The note's Theorem gives a graph of chromatic number $\aleph_1$ with no uncountable, infinitely connected subgraph; the remark marks the countably infinite case as the part of the problem that construction leaves untouched.

Bears on

• Problem 1068: the problem asks whether every graph of chromatic number $\aleph_1$ contains a countable, infinitely vertex-connected subgraph. The problem page reads "countable" as countably infinite, following this remark. Under that reading a positive answer to the remark's question for all uncountably chromatic graphs gives a positive answer to the problem, and a graph of chromatic number $\aleph_1$ with no such subgraph answers both questions negatively. The remark records the question as open as of the note; it carries no progress on the problem.