Erdős problem 1175 · problems.science

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$ ?

Sources

Browse retained paths and inspect the exact material available for this Problem.

5 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

1175.lean

Retained formal statement5 of 5

Threshold reformulation variant. Replaces chromaticCardinal = λ in the hypothesis of erdos_1175 with λ ≤ chromaticCardinal (a graph of chromatic number ≥ λ has a triangle-free subgraph of chromatic number κ). This is a strengthening of erdos_1175 (see erdos_1175.test.threshold_implies_exact).

FormalConjectures/ErdosProblems/1175.leanErdos1175.erdos_1175.variants.threshold_formulation6 linesExact file

1True ↔2  ∀ (κ : Cardinal.{u_1}),3    Cardinal.aleph0 < κ →4      ∃ μ,5        ∀ (V : Type u_1) (G : SimpleGraph V),6          μ ≤ G.chromaticCardinal → ∃ H, H.coe.CliqueFree 3 ∧ H.coe.chromaticCardinal = κ

OpenStatement only, no proof

Sources

Search problems.science