Documentation

FormalConjectures.ErdosProblems.«1176»

Erdős Problem 1176 #

Reference: erdosproblems.com/1176

theorem Erdos1176.erdos_1176 :
sorry ∀ {V : Type u_1} (G : SimpleGraph V), G.chromaticCardinal = Cardinal.aleph 1∃ (EColor : Type) (_ : Cardinal.mk EColor = Cardinal.aleph 1) (c_edge : G.edgeSetEColor), ∀ (VColor : Type), Cardinal.mk VColor Cardinal.aleph 0∀ (c_vert : VVColor), ∃ (vc : VColor), ∀ (ec : EColor), ∃ (u : V) (v : V) (h : G.Adj u v), c_vert u = vc c_vert v = vc c_edge s(u, v), h = ec

Let $G$ be a graph with chromatic number $\aleph_1$. Is it true that there is a colouring of the edges with $\aleph_1$ many colours such that, in any countable colouring of the vertices, there exists a vertex colour containing all edge colours?

A problem of Erdős, Galvin, and Hajnal. The consistency of this was proved by Hajnal and Komjáth.