Skip to content

Erdős problem 918

A question of Erdős and Hajnal [ErHa68b], who proved that for every finite kk there is a graph with chromatic number ℵ1\aleph_1 and ℵk\aleph_k vertices where each subgraph on less than ℵk\aleph_k vertices has chromatic number ≤ℵ0\leq \aleph_0.

Sources

The source's own material, retained exactly.

9 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

918.lean

Retained formal statement4 of 9

Is there a graph with ℵω+1\aleph_{\omega+1} vertices and chromatic number ℵ1\aleph_1 such that every subgraph on ℵω\aleph_\omega vertices has chromatic number ≤ℵ0\leq\aleph_0?

FormalConjectures/ErdosProblems/918.leanErdos918.erdos_918.variants.all_subgraphs.parts.ii6 linesExact file
True ↔  ∀ (ω : Ordinal.{u}),    ∃ V G,      Cardinal.mk V = Cardinal.aleph (ω + 1) ∧        G.chromaticCardinal = Cardinal.aleph 1 ∧          ∀ (H : G.Subgraph), Cardinal.mk ↑H.verts = Cardinal.aleph ω → H.coe.chromaticCardinal ≤ Cardinal.aleph0
OpenStatement only, no proof