erdos_1176

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.

theorem erdos_1176 :
    answer(sorry) ↔ ∀ {V : Type*} (G : SimpleGraph V), G.chromaticCardinal = aleph 1 →
      ∃ (EColor : Type) (_ : mk EColor = aleph 1) (c_edge : G.edgeSet → EColor),
        ∀ (VColor : Type) (_ : mk VColor ≤ aleph 0) (c_vert : V → VColor),
          ∃ (vc : VColor),
            ∀ (ec : EColor), ∃ (u v : V) (h : G.Adj u v),
              c_vert u = vc ∧ c_vert v = vc ∧ c_edge ⟨s(u, v), h⟩ = ec

Recent Submissions

No submissions yet. Be the first to attempt this problem.