For a graph GG, the colouring number col⁡(G)\operatorname{col}(G) is the least cardinal κ\kappa such that the vertices admit a well-ordering in which every vertex has fewer than κ\kappa earlier neighbours; it always bounds the chromatic number from above. In their 1966 paper 'On chromatic number of graphs and set-systems', Erdős and Hajnal proved, assuming GCH, that graphs on at most ωω\omega_\omega vertices with no complete bipartite subgraph [[ω2,ω]][[\omega_2,\omega]] have colouring number at most ω1\omega_1, and asked — as 'the simplest unsolved problem' of their theory (Problem 5.7) — whether the same holds at α=ωω+1\alpha=\omega_{\omega+1}, the first cardinal beyond their induction: under GCH, must every graph on ωω+1\omega_{\omega+1} vertices with no [[ω2,ω]][[\omega_2,\omega]] have colouring number at most ω1\omega_1? The problem remains open under GCH alone. Modern work places it exactly at the boundary between ZFC-provable and cardinal-arithmetic-sensitive phenomena: Bowler, Carmesin, Komjáth and Reiher characterized graphs of large colouring number by forbidden obstructions, observing that which complete bipartite graphs are forced depends on the partition calculus at the relevant cardinals; Usuba proved the positive answer at these parameters from GCH-type arithmetic plus the approachability property APωωAP_{\omega_\omega}, an additional hypothesis not known to follow from GCH, and asked whether his extra assumptions are necessary.

Background

Two cardinal invariants measure how hard a graph is to colour. The chromatic number χ(G)\chi(G) is the least cardinal κ\kappa such that the vertex set can be partitioned into κ\kappa pairwise non-adjacent (independent) sets. The colouring number col⁡(G)\operatorname{col}(G) is the least cardinal κ\kappa such that the vertices admit a well-ordering in which every vertex has fewer than κ\kappa neighbours among its predecessors; always χ(G)≤col⁡(G)\chi(G)\le\operatorname{col}(G). For finite graphs the two notions nearly coincide, but for infinite graphs they genuinely differ, and the colouring number is the finer invariant. Its systematic study originates with the 1966 Erdős–Hajnal paper, and the source records that Rado noticed their proof method naturally yields the colouring-number (stronger) form of their theorems.

For cardinals γ\gamma and δ\delta, [[γ,δ]][[\gamma,\delta]] denotes the complete bipartite graph whose two parts have sizes γ\gamma and δ\delta — the cardinal-level analogue of Km,nK_{m,n}. Erdős and Hajnal introduced the relations: Col⁡(α,β,γ,δ)\operatorname{Col}(\alpha,\beta,\gamma,\delta) asserts that every graph on α\alpha vertices containing no [[γ,δ]][[\gamma,\delta]] has colouring number at most β\beta, and Chr⁡(α,β,γ,δ)\operatorname{Chr}(\alpha,\beta,\gamma,\delta) is the analogous statement for the chromatic number. Since χ≤col⁡\chi\le\operatorname{col}, the colouring-number statement implies the chromatic-number one (Lemma 5.2 of the source). The source states Problem 5.7 disjunctively ('Col or Chr'), but immediately glosses the question with an 'i.e.' clause as the colouring-number claim itself; that glossed form is the one used here, and it is the form taken up in the later literature (Usuba's Proposition 3.11 and Question 3.13).

The set-theoretic backdrop: GCH, the generalized continuum hypothesis, states 2κ=κ+2^\kappa=\kappa^+ for every infinite cardinal κ\kappa. The cofinality cf⁡(κ)\operatorname{cf}(\kappa) is the least size of an unbounded subset of κ\kappa; a cardinal is singular when its cofinality is smaller than itself. The cardinal ωω=sup⁡n<ωωn\omega_\omega=\sup_{n<\omega}\omega_n is singular of countable cofinality, and ωω+1\omega_{\omega+1} is its successor.

Erdős and Hajnal's Theorem 5.5 proves, under GCH, colouring-number statements of the form Col⁡(α,ω1,γ,δ)\operatorname{Col}(\alpha,\omega_1,\gamma,\delta) for α\alpha at most a threshold defined from δ\delta (Definition 5.4 of the source; the threshold is ωω\omega_\omega when δ=ω\delta=\omega). Problem 5.7 asks about the first cardinal not covered by the theorem: ωω+1\omega_{\omega+1}. Their Corollary 5.6 shows, unconditionally, that a graph of uncountable colouring number contains a copy of [[n,ω1]][[n,\omega_1]] for every finite nn, so the jump from finite parts to an ω2\omega_2-sized part is precisely what is at stake.

Modern developments frame the question. Bowler, Carmesin, Komjáth and Reiher characterized graphs of colouring number above μ\mu by two types of forbidden subgraph (a bipartite type and a stationary-set type), and observed that which complete bipartite graphs are forced depends on the partition-calculus properties of the cardinals involved (the partition calculus studies which monochromatic substructures must appear when the subsets of a set are finitely coloured). Usuba proved that every graph XX with col⁡(X)>ω1\operatorname{col}(X)>\omega_1 contains a Kω,ω2K_{\omega,\omega_2} — the same graph as [[ω2,ω]][[\omega_2,\omega]] — provided λω=λ\lambda^\omega=\lambda for every regular uncountable λ<∣X∣\lambda<|X| and the approachability property APλAP_\lambda holds at every singular λ<∣X∣\lambda<|X| of countable cofinality. Approachability is a combinatorial principle about approximating singular cardinals of countable cofinality from below; it follows from weak square principles (weakenings of Jensen's square principle, which asserts the existence of coherent cofinal sequences at a singular cardinal) and is not known to follow from GCH alone. Consequently, Problem 5.7 is answered positively under GCH together with APωωAP_{\omega_\omega}, and remains open under GCH alone — which is exactly what the original problem asks.

Problem Statement

Determine, assuming GCH only, the truth value of Col⁡(ωω+1,ω1,ω2,ω)\operatorname{Col}(\omega_{\omega+1},\omega_1,\omega_2,\omega) in the sense of Erdős and Hajnal (1966): must every graph GG on exactly ωω+1\omega_{\omega+1} vertices that contains no subgraph isomorphic to the complete bipartite graph [[ω2,ω]][[\omega_2,\omega]] (parts of size ω2\omega_2 and ω\omega) have colouring number at most ω1\omega_1? Equivalently: does every graph of size ωω+1\omega_{\omega+1} whose colouring number exceeds ω1\omega_1 contain a [[ω2,ω]][[\omega_2,\omega]]? The source states the question disjunctively — 'is Col(ωω+1,ω1,ω2,ω)(\omega_{\omega+1},\omega_1,\omega_2,\omega) or Chr(ωω+1,ω1,ω2,ω)(\omega_{\omega+1},\omega_1,\omega_2,\omega) true?' — but glosses it with an explicit 'i.e.' clause as the colouring-number claim itself, and that glossed form is the form used here. Since the chromatic number never exceeds the colouring number, a positive answer for the colouring number settles the disjunction affirmatively, while a negative answer to this form must exhibit, in some model of GCH, a graph on ωω+1\omega_{\omega+1} vertices with colouring number greater than ω1\omega_1 and no [[ω2,ω]][[\omega_2,\omega]]. The problem is settled positively under GCH plus the approachability property APωωAP_{\omega_\omega}. Under GCH alone it remains open: it is undecided whether the approachability hypothesis can be eliminated (Usuba's Question 3.13 at these parameters) and undecided whether a GCH-compatible counterexample exists.

References

  1. P. Erdős and A. Hajnal, 'On chromatic number of graphs and set-systems', Acta Mathematica Academiae Scientiarum Hungaricae 17 (1966), 61–99, DOI 10.1007/BF02020444, full text legally archived by the Rényi Institute at https://www.renyi.hu/~p_erdos/1966-07.pdf
  2. Nathan Bowler, Johannes Carmesin, Péter Komjáth, and Christian Reiher, 'The colouring number of infinite graphs', Combinatorica 39 (2019), 1225–1235, DOI 10.1007/s00493-019-4045-9, preprint arXiv:1512.02911v2 (2018) at https://arxiv.org/abs/1512.02911
  3. Toshimichi Usuba, 'The list-chromatic number and the coloring number of uncountable graphs', Israel Journal of Mathematics 259 (2024), 129–167 (published online 2023), DOI 10.1007/s11856-023-2483-y, preprint arXiv:2008.10260v4 (2021) at https://arxiv.org/abs/2008.10260
  4. Chris Lambie-Hanson and Assaf Rinot, 'Reflection on the coloring and chromatic numbers', Combinatorica 39 (2019), 165–214, DOI 10.1007/s00493-017-3741-6, preprint arXiv:1708.06929 (2017) at https://arxiv.org/abs/1708.06929
  5. Saharon Shelah, 'On incompactness for chromatic number of graphs', Acta Mathematica Hungarica 139 (2013), 363–371, DOI 10.1007/s10474-012-0287-3, preprint arXiv:1205.0064 (2012) at https://arxiv.org/abs/1205.0064
  6. Shimon Garti, 'List chromatic numbers and singular compactness', arXiv:2111.11826 (2021, latest version revised 2025), https://arxiv.org/abs/2111.11826
  7. Péter Komjáth, 'A note on chromatic number and connectivity of infinite graphs', Israel Journal of Mathematics 196 (2013), 499–506, DOI 10.1007/s11856-012-0176-z, https://link.springer.com/article/10.1007/s11856-012-0176-z
  8. Dániel T. Soukup, 'Trees, ladders and graphs', Journal of Combinatorial Theory, Series B 115 (2015), 96–116, DOI 10.1016/j.jctb.2015.05.004, preprint arXiv:1409.2922 (2014) at https://arxiv.org/abs/1409.2922
  9. Carsten Thomassen, 'Infinitely connected subgraphs in graphs of uncountable chromatic number', Combinatorica 37 (2017), 785–793, DOI 10.1007/s00493-016-3436-4, https://link.springer.com/article/10.1007/s00493-016-3436-4
  10. Nathan Bowler and Max Pitz, 'A note on uncountably chromatic graphs', arXiv:2402.05984 (2024), https://arxiv.org/abs/2402.05984
  11. Hong Liu and Richard Montgomery, 'A solution to Erdős and Hajnal's odd cycle problem', Journal of the American Mathematical Society 36 (2023), 1191–1234, DOI 10.1090/jams/1018, preprint arXiv:2010.15802 (2020) at https://arxiv.org/abs/2010.15802