Problem 1067

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

Source: erdosproblems.com/1067

Graph theory
Set theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

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.

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.

Problem 1067

Status

Proof claims

Discussion