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

Updated Oct 7

Problem 1175

Statement. Let $\kappa$ be an uncountable cardinal. Must there exist a cardinal $\lambda$ such that every graph with chromatic number $\lambda$ contains a triangle-free subgraph with chromatic number $\kappa$ ?

Status. Open.

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

Formalization. Statement in formal-conjectures.

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 (13)

Problem 740 Komjáth and Shelah's consistent counterexample at aleph one Negative answer in ZFC at aleph_1 and r = 3 Set Theory and Infinite Combinatorics set_theory/komjath_1988_forcing_constructions_uncountably_chromatic_graphs Theorem 1: an aleph_1-chromatic graph whose subgraphs omitting K(omega+1) are countably chromatic Theorem 2: under CH, an uncountably chromatic graph with only countably chromatic triangle-free subgraphs Theorem 3: a K(4)-free aleph_1-chromatic graph with only countably chromatic triangle-free subgraphs Theorem 4: a K(4)-free graph of chromatic number above the continuum has an uncountably chromatic triangle-free subgraph set_theory/komjath_2002_finite_subgraphs_uncountably_chromatic_graphs set_theory/komjath_2025_erdos_hajnal_problem_list set_theory/soukup_2015_open_problems_around_uncountable_graphs Conjecture 2.1 (p. 1): an omega_1-chromatic graph whose uncountably chromatic subgraphs all contain triangles (Erdős–Hajnal)

Graph