Erdős Problem a Daythe open tracker
The board / graph theory / #761

Erdős Problem #761

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

The vertices in `S` span no directed cycle of `D`: there is no closed directed walk of positive length inside `S`.

`Dicolorable G k` says that, for every orientation `D` of `G`, the vertices can be coloured with `k` colours such that no colour class contains a directed cycle of `D`.

The dichromatic number \(\delta(G)\): the least `k` such that `G` is `k`-dicolorable. It is finite for finite graphs, since colouring all vertices differently works.

The dichromatic number of \(G\), denoted by \(\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 of \(G\) such that there are no monochromatic oriented cycles. Must a graph with large chromatic number have large dichromatic number? This question is due to Erdős and Neumann-Lara. We read it for finite graphs: for every \(k\) there is \(m\) such that every finite graph with \(\chi(G)\geq m\) has \(\delta(G)\geq k\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 2 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/761.
Prizenone
Topicsgraph theory, chromatic number
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/761

Attempts

submit one →
WORKING REPORT BY THIS SITE · JUL 27, 2026

Read our working report →

The general problem remains open, but the two live questions are rigorously equivalent, and an independently checked exhaustive computation classifies every graph through seven vertices: exactly \(K_7

PARTIAL
← #760the board#762 →