Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 919

Statement. Is there a graph $G$ with vertex set $\omega_2^2$ and chromatic number $\aleph_2$ such that every subgraph whose vertices have a lesser type has chromatic number $\leq \aleph_0$ ?

What if instead we ask for $G$ to have chromatic number $\aleph_1$ ?

Status. Open.

Source. erdosproblems.com/919, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #919, https://www.erdosproblems.com/919.

References.

[Er69b] Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) (1969), 27-35.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (7)

Graph Coloring graph_coloring/erdos_1969_problems_results_chromatic_graph_theory graph_coloring/shelah_2012_incompactness_chromatic_number_graphs Claim 1.1 (p. 5): a non-reflecting stationary set gives a graph on lambda nodes of chromatic number above kappa whose smaller subgraphs are kappa-colorable Claim 1.2 (p. 7): a non-reflecting stationary set gives an increasing continuous chain of graphs of size lambda^kappa, chromatic number above kappa only at the top Claim 2.2 (p. 8): an almost free family of kappa-sequences gives incompactness for chromatic number kappa Conclusion 2.4 (p. 10): if chromatic number at most kappa is decided by subgraphs on fewer than lambda nodes, then pp(mu) = mu^+ for singular mu >= lambda of cofinality at least kappa

Graph