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

Updated Oct 7

Problem 1068

Statement. Does every graph with chromatic number $\aleph_1$ contain a countable subgraph which is infinitely vertex-connected?

Formulation. Under the site's definition of infinite connectivity (any two vertices joined by infinitely many pairwise vertex-disjoint paths), a subgraph with a single vertex qualifies vacuously, which would make the question trivial. The question is read as its sources read it, as asking for a countably infinite, infinitely connected subgraph. Bowler and Pitz pose it so in Remark (3) of their note [BoPi24], for every uncountably chromatic graph. The formal-conjectures statement requires at least two vertices in its definition of infinite connectivity, and two vertices joined by infinitely many disjoint paths need infinitely many vertices, so the formal statement is not trivial. The open status concerns that reading.

Status. Open.

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

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.
[So15] Soukup, Dániel T., Trees, ladders and graphs. J. Combin. Theory Ser. B (2015), 96-116.
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999).

Formalization. Statement in formal-conjectures.

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

Set Theory and Infinite Combinatorics set_theory/bowler_2024_note_uncountably_chromatic_graphs Remark (3): the countable version of the Erdős-Hajnal problem 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

Graph