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 statement2 of 5

Every graph has a triangle-free subgraph: the bottom subgraph (with no edges) witnesses triangle-freeness, so the existential ∃ H : G.Subgraph, H.coe.CliqueFree 3 in erdos_1175 is non-vacuous.

FormalConjectures/ErdosProblems/1175.leanErdos1175.erdos_1175.test.exists_triangle_free_subgraph1 lineExact file

1∀ (V : Type u_1) (G : SimpleGraph V), ∃ H, H.coe.CliqueFree 3

TestStatement only, no proof

Sources

Search problems.science