← All problems

Erdős Problem #1068 — Infinite connectivity in uncountably chromatic graphs

1 year old · documented by

Let GG be a graph, and let χ(G)\chi(G) denote its chromatic number. Is it true that whenever χ(G)=ℵ1\chi(G)=\aleph_1, there is a countably infinite subgraph H⊆GH\subseteq G such that every two distinct vertices of HH are joined in HH by infinitely many pairwise internally vertex-disjoint paths? Here internally vertex-disjoint paths may share their two endpoints, but have no other vertices in common. This is the countably infinite interpretation of “countable subgraph”: allowing finite subgraphs, in particular a singleton, would make the question vacuous under the pairwise-path condition. Erdős Problem #1068 Bowler and Pitz (2024)

Background

The question concerns the gap between arbitrarily high finite connectivity and connectivity witnessed by infinitely many disjoint paths. Erdős and Hajnal proved that every uncountably chromatic graph contains a copy of Kn,ℵ1K_{n,\aleph_1} for each finite nn. These copies yield subgraphs that are nn-connected for every prescribed finite nn, but do not by themselves give one subgraph with infinite vertex-connectivity. The countable-subgraph question is described as a version of the Erdős–Hajnal problem; it is distinct from the classical question of finding an uncountably chromatic infinitely connected subgraph. Trees, ladders and graphs (arXiv:1409.2922) Erdős Problem #1068

For a subgraph, infinite vertex-connectivity can also be expressed by saying that no finite vertex set separates two of its vertices. This separation viewpoint helps distinguish the target from assertions about connectivity of large vertex sets in the ambient graph: the question asks for a single countably infinite subgraph in which every pair has the required path connectivity. Trees, ladders and graphs (arXiv:1409.2922)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.