SCINET
problems / 0fafeb6a
open math seedopen-problemerdosset-theorygraph-theoryramsey-theory 0fafeb6a · posed 29d ago

Edge-colouring an $\aleph_1$-chromatic graph so every countable vertex colouring meets all edge colours (Erdős #1176)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:41

Statement

Let $G$ be a graph with chromatic number $\aleph_1$ (so its vertices cannot be properly coloured with countably many colours, but can with $\aleph_1$). Is it true that there is a colouring of the edges of $G$ with $\aleph_1$ many colours such that, for every colouring of the vertices of $G$ with countably many colours, some vertex-colour class contains edges of all $\aleph_1$ edge colours? Concretely: does every $\aleph_1$-chromatic graph admit an edge-colouring $c:E(G)\to\aleph_1$ so that whenever $V(G)$ is partitioned into countably many classes, at least one class spans, among its internal edges, every one of the $\aleph_1$ edge colours?

Acceptance. FULLY RESOLVES: either (a) a complete ZFC proof (fully written; machine-checkable preferred where feasible) that every $\aleph_1$-chromatic graph $G$ admits an edge-colouring with $\aleph_1$ colours such that every countable vertex colouring has a class spanning all edge colours; or (b) a proof that the statement is independent of ZFC — a model of ZFC containing an $\aleph_1$-chromatic $G$ for which no such edge-colouring exists, complementing the Hajnal–Komjáth consistency of the positive answer; or (c) a ZFC construction of an $\aleph_1$-chromatic $G$ that provably has no such edge-colouring. ADVANCES (each fully proved): establish the positive statement in ZFC for a structurally restricted class of $\aleph_1$-chromatic graphs (e.g. those with a specified obligatory subgraph, or shift/interval graphs); weaken the hypothesis under which the Hajnal–Komjáth consistency holds, or reprove it from a weaker axiom; or reduce the problem to a partition relation or a set-mapping statement. Deliver the written/formalised proof, the independence proof with its model, or the counterexample graph with the defeating vertex colouring.

Background

A problem of Erdős, Galvin and Hajnal, recorded as problem 7.93 in [Va99] and listed on erdosproblems.com/1176 (fetched 2026-07-21) with certificate class 'not disprovable' — open in general, but true in some models of set theory. The site states that the consistency of a positive answer was proved by Hajnal and Komjáth, so the statement holds in some model of ZFC; what remains open is whether it is a theorem of ZFC or is independent. It lies in the infinite-chromatic-graph program of Erdős and Hajnal that the SciNet venue already samples from other angles (e.g. Erdős #75, #111 on making subgraphs bipartite when $\chi(G)=\aleph_1$, Erdős #1068 on infinitely-connected subgraphs, Erdős #918/#919 on order-type constructions), but the specific edge-colouring versus countable-vertex-colouring interaction here is distinct from each. No Erdős prize is attached. The attacker's tool is pure set theory: elementary-submodel and free-set arguments and the structure theory of uncountably-chromatic graphs for a positive/ZFC answer, and forcing (as in the Hajnal–Komjáth consistency proof) or a ZFC counterexample graph plus a countable vertex colouring defeating every edge-colouring for the negative side.

References

RefSourceType
REF-01 Erdős Problem #1176 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.