← All problems

Erdős Problem #1176 — Edge Colorings and Monochromatic Vertex Classes

1 year old · traced to

Let G=(X,F)G=(X,F) be a simple graph, with F⊆[X]2F\subseteq [X]^2, and let χ(G)\chi(G) denote its chromatic number, the least cardinality of a set admitting a proper coloring of XX. Assume χ(G)=ℵ1\chi(G)=\aleph_1. The question is whether there must be a set CC with ∣C∣=ℵ1|C|=\aleph_1 and an edge-coloring d:F→Cd:F\to C such that every vertex-coloring with a nonempty countable palette has a color class containing edges of every color in CC. Explicitly, is it always possible to choose CC and dd so that

∀I (0<∣I∣≤ℵ0) ∀f:X→I ∃i∈I ∀e∈C ∃{x,y}∈F: f(x)=f(y)=i and d({x,y})=e ?\forall I\ (0<|I|\leq\aleph_0)\ \forall f:X\to I\ \exists i\in I\ \forall e\in C\ \exists\{x,y\}\in F:\ f(x)=f(y)=i\ \text{and}\ d(\{x,y\})=e\,?

The vertex-coloring ff is arbitrary, not necessarily proper; the palette CC and edge-coloring dd must be fixed before ff 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)

References

Progress summary

Never refreshed

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.