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

Source: erdosproblems.com/1176

Set theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. The site labels the problem NOT DISPROVABLE, and its remark credits Hajnal and Komjáth with the consistency. The accepted partial claim Hajnal and Komjáth's consistency result shows that the statement holds in a model of ZFC, so ZFC does not refute it, one side of an independence result; whether ZFC proves the statement is open. The page departs from the site's label because one side alone leaves the question open.

ErGaHa75: Erdős, P., Galvin, F. and Hajnal, A., On set-systems having large chromatic number and not containing prescribed subsystems. In: Infinite and finite sets (Colloq., Keszthely, 1973), Vol. I, Colloq. Math. Soc. János Bolyai 10, North-Holland, Amsterdam, 1975, pp. 425-513; §6, Problem 3. Library home: Erdős, Galvin and Hajnal 1975.
HaKo03: Hajnal, András and Komjáth, Péter, Some remarks on the simultaneous chromatic number. Combinatorica 23 (2003), 89-104. DOI 10.1007/s00493-003-0015-2.
So15: Soukup, Dániel T., Open problems around uncountable graphs. Workshop handout, Independence Results in Mathematics and Challenges in Iterated Forcing, University of East Anglia, November 2015; §6, Conjecture 6.1, which states the conjecture in the catalog's form (attributed there to Erdős and Hajnal) and records that it holds consistently, adding a single Cohen real sufficing, citing [HaKo03]. A secondary source. Library home: Soukup 2015.
Va99: Some of Paul's favorite problems, booklet for the conference "Paul Erdős and his mathematics", Budapest, July 1999; item 7.93, which asks the question and remarks that Hajnal and Komjáth showed its consistency. Library home: Various 1999.

Problem 1176

Status

Proof claims

Discussion