Wiki
Wiki

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

Updated


Claim. It is consistent with ZFC that some graph with ℵ1\aleph_1 vertices and chromatic number ℵ1\aleph_1 has no uncountable set of vertices spanning an infinitely connected subgraph. A subgraph of chromatic number ℵ1\aleph_1 is uncountable, so such a graph has no infinitely connected subgraph of chromatic number ℵ1\aleph_1, and ZFC does not prove the positive answer to Problem 1067. This is Péter Komjáth, A note on chromatic number and connectivity of infinite graphs, Israel J. Math. 196 (2013), no. 1, 499--506. It obtains the graph by forcing and corrects the forcing of the author's Consistency results on infinite graphs, Israel J. Math. 61 (1988), 285--294. The statement follows the introductions of Soukup (arXiv:1409.2922v1) and of Bowler and Pitz (arXiv:2402.05984v2), which describe the result.

Covers. The unprovability of the positive answer, through a model in which it fails. Soukup's ZFC counterexample supersedes it. The same model answers no to the 1966 version for graphs with ℵ1\aleph_1 vertices. Komjáth's 1988 paper shows that under the Proper Forcing Axiom every graph of size and chromatic number ℵ1\aleph_1 has an uncountably chromatic infinitely connected subgraph, so that variant is independent of ZFC, as the site records. The variant is not the problem's question.

Acceptance. Refereed: the result is a journal paper in the Israel Journal of Mathematics. The site's curator credits Komjáth with the consistency of a negative answer. The label DISPROVED (LEAN) rests on the later ZFC counterexamples, so that credit is not listed as reviewed.