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 vertices and chromatic number has no uncountable set of vertices spanning an infinitely connected subgraph. A subgraph of chromatic number is uncountable, so such a graph has no infinitely connected subgraph of chromatic number , 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 vertices. Komjáth's 1988 paper shows that under the Proper Forcing Axiom every graph of size and chromatic number 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.