Erdős Problem #1176 — Edge Colorings and Monochromatic Vertex Classes
Let be a simple graph, with , and let denote its chromatic number, the least cardinality of a set admitting a proper coloring of . Assume . The question is whether there must be a set with and an edge-coloring such that every vertex-coloring with a nonempty countable palette has a color class containing edges of every color in . Explicitly, is it always possible to choose and so that
The vertex-coloring is arbitrary, not necessarily proper; the palette and edge-coloring must be fixed before is chosen. Erdős Problems #1176 Hajnal and Komjáth (2003) Soukup (2015)
Background
This question, attributed to Erdős, Galvin, and Hajnal, is listed as problem 7.93 in the reference identified by the problem listing. It is framed as a simultaneous chromatic-number problem: one edge-coloring must work against every countable coloring of the vertices. For each such vertex-coloring, a single class must realize the entire edge-color palette, rather than merely having all edge colors occur somewhere in the graph. Hajnal and Komjáth’s 2003 paper presents this as a conjecture and discusses partial results, variants, and consistency results. Erdős Problems #1176 Hajnal and Komjáth (2003)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.