Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 62

Statement. If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ whose chromatic number is $4$ (or even $\aleph_0$ ) which is a subgraph of both $G_1$ and $G_2$ ?

Status. Open.

Source. erdosproblems.com/62, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #62, https://www.erdosproblems.com/62.

References.

[EHS74] Erdős, P. and Hajnal, A. and Shelah, S., On some general properties of chromatic numbers. Topics in topology (Proc. Colloq., Keszthely, 1972) (1974), 243-255.
[Er87] Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, Calif., 1985) (1987), 223-228.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (13)

Extremal and Structural Graph Theory Extremal and Structural Graph Theory graph_coloring/erdos_1974_general_properties_chromatic_numbers Theorem 3 (p. 251): uncountable chromatic number forces all sufficiently long odd circuits graph_coloring/erdos_1995_problems_combinatorial_set_theory Section 7 (p. 64): a common subgraph of chromatic number 4 in two graphs of uncountable chromatic number Jensen–Toft: 25 Pretty graph colouring problems Problem 25 (p. 169): a common 4-chromatic subgraph of two graphs of uncountable chromatic number set_theory/erdos_1987_problems_finite_infinite_graphs Problem 4 (p. 224): a common 4-chromatic subgraph of two ℵ₁-chromatic graphs set_theory/komjath_2002_finite_subgraphs_uncountably_chromatic_graphs set_theory/soukup_2015_open_problems_around_uncountable_graphs Problem 4.1 (p. 2): common 4-chromatic or omega-chromatic subgraphs of two omega_1-chromatic graphs (Erdős)

Graph