Does large chromatic or cochromatic number force large dichromatic number? (Erdős #761)
Statement
The cochromatic number of a graph $G$, denoted $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ so that each colour class induces either a complete graph or an empty graph. The dichromatic number of $G$, denoted $\delta(G)$, is the minimum number $k$ of colours required such that, in any orientation of the edges of $G$, there is a $k$-colouring of the vertices with no monochromatic oriented cycle. Must a graph with large chromatic number have large dichromatic number — i.e. does $\chi(G)\to\infty$ force $\delta(G)\to\infty$? Must a graph with large cochromatic number contain a subgraph with large dichromatic number?
Acceptance. FULLY RESOLVES: a proof that for every $k$ there is $r(k)$ such that $\chi(G)\geq r(k)$ implies $\delta(G)\geq k$ (first question), or of the stronger cochromatic statement (second question); OR a refutation — an explicit infinite family with unbounded chromatic (resp. cochromatic) number and uniformly bounded dichromatic number, with full proofs of both properties. Machine-checkable (Lean/Coq) proof preferred, else a complete written proof. ADVANCES: (a) exhibit a finite $c$ such that $\chi(G)\geq c$ forces $\delta(G)\geq 3$ (the first nontrivial threshold); (b) prove either implication for a natural restricted class (e.g. bounded clique number, Kneser-type families); (c) verified computations of dichromatic numbers of concrete structured families that materially map the frontier, with code and a per-graph certificate (an orientation plus an exhaustive or SAT-certified check); (d) a proof clarifying the second question's relation to the first beyond the known one-way implication. Deliver the proof file, or the counterexample family with proofs, or the computation code plus certificates.
Background
The first question is due to Erdős and Neumann-Lara (the Erdős–Neumann-Lara conjecture, going back to the late 1970s/1980s); the second is due to Erdős and Gimbel [ErGi93]. Both are listed as open on erdosproblems.com/761 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). A positive answer to the second question implies a positive answer to the first, via the comparison between chromatic and cochromatic numbers recorded at Erdős #760 (erdosproblems.com/760). The Erdős–Neumann-Lara conjecture is a central difficulty in digraph colouring: even its first nontrivial instance — exhibiting any finite chromatic threshold that forces dichromatic number $3$ — appears to remain open in the published literature, while Mohar and Wu (2016) proved a fractional analogue (large fractional chromatic number forces large dichromatic number). Note that a negative answer requires an infinite family: graphs of unbounded chromatic (or cochromatic) number in which every orientation of every member admits a colouring with few colour classes each inducing no directed cycle. The attacker's tool: exact dichromatic-number computation (SAT/ILP with acyclicity constraints) on structured candidate families — Kneser graphs, shift graphs, random graphs — to map where small dichromatic number can coexist with large chromatic number, plus extremal proofs for restricted classes.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #761 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #760 (T. F. Bloom) — chromatic vs cochromatic comparison used in the implication | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.