← All problems

Erdős Problem #918 — Highly chromatic graphs with countably chromatic large subgraphs

58 years old · traced to

A graph here is a simple undirected graph G=(V,E)G=(V,E), with E⊆[V]2E\subseteq [V]^2, and χ(G)\chi(G) denotes its chromatic number. A subgraph may use any subset of the edges on its vertex set. Since passing to the induced subgraph can only increase chromatic number, the local conditions below are equivalently conditions on every vertex subset of the stated size. The questions are whether there exists a graph satisfying each of the following specifications: Erdős Problems #918 Erdős–Hajnal (1968)

∣V(G)∣=ℵ2,χ(G)=ℵ2,and χ(H)≤ℵ0 for every subgraph H⊆G with ∣V(H)∣=ℵ1;|V(G)|=\aleph_2,\qquad \chi(G)=\aleph_2,\qquad \text{and }\chi(H)\leq\aleph_0\text{ for every subgraph }H\subseteq G\text{ with }|V(H)|=\aleph_1;

Erdős Problems #918 Erdős–Hajnal (1968)

and Erdős Problems #918 Erdős–Hajnal (1968)

∣V(G)∣=ℵω+1,χ(G)=ℵ1,and χ(H)≤ℵ0 for every subgraph H⊆G with ∣V(H)∣=ℵω.|V(G)|=\aleph_{\omega+1},\qquad \chi(G)=\aleph_1,\qquad \text{and }\chi(H)\leq\aleph_0\text{ for every subgraph }H\subseteq G\text{ with }|V(H)|=\aleph_\omega.

Erdős Problems #918 Erdős–Hajnal (1968)

The equalities in the local size conditions are intentional; the associated results below sometimes concern all subgraphs below a threshold instead. Erdős Problems #918 Erdős–Hajnal (1968)

Background

Erdős and Hajnal introduced this family of questions in their work on chromatic numbers of infinite graphs and related set-theoretic partition problems. Their motivating general problem asks when a graph can have large chromatic number even though all subgraphs induced by sufficiently small vertex sets have bounded chromatic number. They developed a construction using a partition theorem, and their paper records partial results under the generalized continuum hypothesis (GCH). Erdős–Hajnal (1968)

A related formulation in Erdős’s 1969 problem list appears to have specified chromatic number ℵ0\aleph_0; the problem page notes that this cannot be the intended version when “subgraph” has its ordinary meaning, since a graph with countable chromatic number has only subgraphs of countable chromatic number. The formulation considered here instead requires uncountable chromatic number, as in the Erdős–Hajnal version. Erdős Problems #918

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.