---

Statement

Problem 4 (printed p. 224), quoted: "Is it true that if $G_1$ and $G_2$ are $\aleph_1$-chromatic graphs then they have a common 4-chromatic subgraph? Perhaps they have a common $\aleph_0$-chromatic subgraph as well."

The item goes on to record, without proof or result:

• that Erdős cannot exclude a family of $\aleph_0$ graphs $G_n$ ($n<\omega$), each of chromatic number $\aleph_1$, no two of which have a common 4-chromatic subgraph;
• that it seems more likely that any finite set of $\aleph_1$-chromatic graphs has a common 4-chromatic (perhaps $\aleph_0$-chromatic) subgraph;
• the guess that every $\aleph_1$-chromatic graph $G$ contains every 4-chromatic graph all of whose circuits have length greater than some $n_G$, which an old result of Erdős, Hajnal and Shelah shows for three-chromatic graphs.

Source. P. Erdős, Some problems on finite and infinite graphs, Logic and Combinatorics (Arcata, Calif., 1985), Contemp. Math. 65, Amer. Math. Soc. (1987), 223--228; Problem 4, p. 224, PDF p. 2 of the Rényi archive's scan (printed p. $n$ = PDF p. $n-222$), read on the rendered page image. The edition read is identified in the source digest.

Read depth. Claims checked: the item was read clause by clause on the page image. It poses questions and cites one result without proof.

Proof pointer

None in the source.

Dependencies

None.

Bears on

• Problem 62: the opening question and its $\aleph_0$-chromatic strengthening are this problem's question, cited there as [Er87]. The paper records no result on it.