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

Updated Oct 8

Problem 110

claims/: The 2 claim pages of Problem 110, one per claimant's result; the problem's standing derives from them.

Statement. Is there some $F(n)$ such that every graph with chromatic number $\aleph_1$ has, for all large $n$ , a subgraph with chromatic number $n$ on at most $F(n)$ vertices?

Status. Disproved on the site (label DISPROVED; page last edited 1 October 2025). The site attributes the conjecture to Erdős, Hajnal and Szemerédi [EHS82], notes that it fails for graphs of chromatic number $\aleph_0$ , recalls that de Bruijn and Erdős [dBEr51] guarantee a finite subgraph of every finite chromatic number inside any graph of infinite chromatic number, records Erdős's view in [Er95d] that the answer should be yes with an $F$ growing faster than every iterated exponential, and credits Shelah [KoSh05] (a paper joint with Komjáth) with the consistency of a negative answer and Lambie-Hanson [La20] with a counterexample in ZFC. The standing rests on [[problems/graph_coloring/E0110/claims/2019_02_21_lambie_hanson|Lambie-Hanson's theorem]], accepted on its refereed publication and the curator's credit: for every function $f$ there is a graph of chromatic number $\aleph_1$ in which, for every $k\ge3$ , every subgraph of chromatic number at least $k$ has at least $f(k)$ vertices, so no $F$ works. The [[problems/graph_coloring/E0110/claims/2002_12_04_komjath_shelah|Komjáth–Shelah forcing result]] is an accepted partial claim: it showed the positive answer unprovable in ZFC without deciding the question.

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

References.

[EHS82] Erdős, P. and Hajnal, A. and Szemerédi, E., On almost bipartite large chromatic graphs. Theory and practice of combinatorics (1982), 117-123.
[Er95d] Erdős, Paul, On some problems in combinatorial set theory. Publ. Inst. Math. (Beograd) (N.S.) 57(71) (1995), 61-65.
[KoSh05] Komjáth, Péter and Shelah, Saharon, Finite subgraphs of uncountably chromatic graphs. J. Graph Theory (2005), 28-38.
[La20] Lambie-Hanson, Chris, On the growth rate of chromatic numbers of finite subgraphs. Adv. Math. (2020), 107176, 13.
[dBEr51] de Bruijn, N. G. and Erdős, P., A colour problem for infinite graphs and a problem in the theory of relations. Indag. Math. (1951), 369-373.

Formalization. No statement file in the formal-conjectures catalog. A Lean 4 file in Boris Alexeev's lean-proofs collection, added 2026-08-17, declares itself a formalization of Lambie-Hanson's solution with Codex and GPT-5.6 Sol as its formal authors; it is linked from the claim page and was not built by this corpus.

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 (25)

Komjáth and Shelah show a positive answer is unprovable problems/graph_coloring/E0110/claims Graph Coloring Graph Coloring graph_coloring/bruijn_1951_colour_problem_infinite_graphs_problem_theory Compactness of finite graph colourings graph_coloring/erdos_1982_almost_bipartite_large_chromatic_graphs Corollary 1.4: n-vertex subgraphs of the k-edge graph have chromatic number at most c_k log^{(k-1)} n Problem 1: which f bound the chromatic numbers of n-vertex subgraphs of arbitrarily large chromatic graphs graph_coloring/erdos_1995_problems_combinatorial_set_theory Section 3 (pp. 62–63): the Erdős–Hajnal–Szemerédi problems on almost bipartite graphs of large chromatic number graph_coloring/lambiehanson_2020_growth_rate_chromatic_numbers_finite_subgraphs Question 1.2 (p. 2): for every f, is there an uncountably chromatic graph with f(k)/f_G(k) -> 0? Answered yes in ZFC Theorem 1.1 (pp. 1-2): Erdős-Hajnal shift graphs G_0(alpha,n,s) have chromatic number above kappa for large alpha, and k-vertex subgraphs of G_0(alpha,n,1) have chromatic number at most c_n log^(n-1)(k)Theorem A (p. 2): in ZFC, for every f there is a graph of size 2^aleph_1 and chromatic number aleph_1 with f_G(k) >= f(k) for all k >= 3 Theorem B (p. 2): under diamond, for every f there is a Hajnal-Mate graph with |G| = chi(G) = aleph_1 and f_G(k) >= f(k) for all k >= 3 Rado (1949): Axiomatic treatment of rank in infinite sets Lemma 1: Rado's finite-choice selection principle set_theory/erdos_1987_problems_finite_infinite_graphs Problem 6 (p. 225): ℵ₁-chromatic graphs whose n-chromatic subgraphs must be large set_theory/komjath_2002_finite_subgraphs_uncountably_chromatic_graphs Theorem 1 (p. 7): the forcing Q^f adds an uncountably chromatic graph on ω_1 whose subgraphs on at most f(r) vertices are at most 2^{r+1}-chromatic Theorem 2 (p. 7): consistently with CH, for every f there is an uncountably chromatic graph on ω_1 whose subgraphs on f(r) vertices are at most r-chromatic set_theory/soukup_2015_open_problems_around_uncountable_graphs Conjecture 3.1 (p. 2): uncountably chromatic graphs whose n-chromatic subgraphs have at least f(n) vertices (Erdős)

Graph