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

Updated Oct 8

Problem 1067

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

Statement. Does every graph with chromatic number $\aleph_1$ contain an infinitely connected subgraph with chromatic number $\aleph_1$ ?

Status. DISPROVED (LEAN). The Lean suffix is the site's catalog label. The site's commentary credits the counterexamples to Soukup and, in a simpler form, to Bowler and Pitz, and the frontmatter standing is derived from the accepted claim pages Soukup's ZFC counterexample and Bowler and Pitz's elementary counterexample, each accepted on its refereed publication and the site's credit; the Lean development the suffix refers to is recorded on the second page as a formalization link, not as formalized evidence. Komjáth's earlier consistency result has its own partial claim page, Komjáth's forced counterexample.

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

References.

[BoPi24] N. Bowler and M. Pitz, A note on uncountably chromatic graphs. arXiv:2402.05984 (2024).
[ErHa66] Erdős, P. and Hajnal, A., On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar. (1966), 61-99.
[ErHa85] Erdős, Paul and Hajnal, András, Chromatic number of finite and infinite graphs and hypergraphs. Discrete Math. (1985), 281-285.
[Ko13] Komjáth, Péter, A note on chromatic number and connectivity of infinite graphs. Israel J. Math. (2013), 499-506.
[So15] Soukup, Dániel T., Trees, ladders and graphs. J. Combin. Theory Ser. B (2015), 96-116.
[Th17] Thomassen, Carsten, Infinitely connected subgraphs in graphs of uncountable chromatic number. Combinatorica (2017), 785-793.

Formalization. Statement in formal-conjectures (revision of 2026-10-07), which states the main question as erdos_1067 with the answer false in the category research solved, names as its formal proof a development in an outside repository, recorded on the claim page, and records the edge-connectivity variant, answered yes by Thomassen [Th17], as a second solved statement. The site's commentary says instead that Thomassen constructed a counterexample to the edge-connectivity version. That is an error of the site: Theorem 2 of Thomassen's paper (Combinatorica 37 (2017), 785--793) proves that every graph of uncountable chromatic number has a subgraph of uncountable chromatic number and infinite edge-connectivity, and inside a graph of chromatic number $\aleph_1$ such a subgraph has chromatic number exactly $\aleph_1$ .

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

Komjáth's forced counterexample of size aleph one Soukup's ZFC counterexample from trees and ladders Bowler and Pitz's elementary counterexample problems/set_theory/E1067/claims Set Theory and Infinite Combinatorics set_theory/bowler_2024_note_uncountably_chromatic_graphs Theorem (p. 1, unnumbered): an uncountably chromatic graph with no uncountable, infinitely connected subgraph set_theory/erdos_1966_chromatic_number_graphs_set_systems Assertion on p. 77: ω-fold connected subgraphs at chromatic number ω₁ set_theory/soukup_2015_open_problems_around_uncountable_graphs Conjecture 1.1 (p. 1): an omega_1-chromatic graph with no nonempty infinitely connected subgraph (Erdős–Hajnal)set_theory/soukup_2015_trees_ladders_graphs Problem 6.4: must an uncountably chromatic graph contain an omega-connected subset?Theorem 3.5: an omega_1-chromatic graph with no uncountable omega-connected set Theorem 4.3: an omega_1-chromatic subgraph of G(T(S)) separating incomparable points finitely

Graph