Erdős problem 761 — live audit, equivalence, and the exact order-seven frontier

Date: 2026-07-27 UTC

Claim labels used below:

• (a) elementary-rigorous: proved here without an external theorem.
• (b) rigorous-modulo-named-theorem: the deduction uses the named, source-checked theorem.
• (c) plausible/structural-unverified: a diagnosis or proposed direction, not a theorem.
• (d) computational-only: exhaustive computation with the standalone verifier stated.

0. Mandatory live-page check

(d; direct browser observation.) I fetched the live

Erdős problem 761 page through the Bright

Data browser path on 2026-07-27. I also fetched its LaTeX-source view and

discussion thread. I did not

infer the statement from the stale tracker metadata.

The statement, verbatim from the live LaTeX-source view, is:

> The cochromatic number of \(G\), denoted by \(\zeta(G)\), is the minimum number of colours needed to colour the vertices of \(G\) such that each colour class induces either a complete graph or empty graph. 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? Must a graph with large cochromatic number contain a graph with large dichromatic number?

The relevant live-page state was:

• Status: OPEN.
• 0 claimed proofs for this problem.
• Interested in collaborating: None.
• Currently working on this problem: None.
• Likes this problem: None.
• Both “looks difficult” and “looks tractable”: None.
• Both formalisation-work markers: None; formalised statement: No.
• Citation: [ErGi93] = P. Erdős and J. Gimbel, *Some problems and results in

cochromatic theory, Quo vadis, graph theory?* (1993), 261–264, MR 1217997.

The page's listed background says that the first question is due to Erdős and

Neumann-Lara, the second to Erdős and Gimbel, and that a positive answer to the

second implies one to the first via problem 760.

There is one comment, by AronBhalla at 00:28 on 26 April 2026. It claims that

the two questions are actually equivalent: the missing direction follows from

\(\zeta(G)\leq\chi(G)\), applying the first question to \(G\) itself. The site

labels comments unverified. Section 1 independently checks this argument and

the other direction.

The stop condition was therefore not triggered: the page is open, has no

claimed proof, and lists no current worker or interested collaborator.

1. Precise formulation and equivalence of the two questions

For an orientation \(D\), write \(\vec\chi(D)\) for the least number of

acyclic vertex classes covering \(V(D)\). The live definition is equivalently

Here and below, “contains a subgraph” uses the standard convention allowing

the subgraph to equal the host.

Monotonicity

(a) If \(H\subseteq G\), then

Indeed, extend any orientation of \(H\) arbitrarily to an orientation of

\(G\). Any dicolouring of the extension restricts to one of \(H\). Maximising

first over orientations of \(H\) proves (1).

Threshold formulation

For an integer \(r\), let:

• \(A_r\): there is a finite \(C_r\) such that

\(\chi(G)\geq C_r\Rightarrow\delta(G)\geq r\);

• \(B_r\): there is a finite \(Z_r\) such that

\(\zeta(G)\geq Z_r\Rightarrow G\) contains \(H\) with

\(\delta(H)\geq r\).

The first live question asks whether every \(A_r\) holds, and the second asks

whether every \(B_r\) holds.

(a) \(A_r\Rightarrow B_r\). Every proper colouring is a cochromatic

colouring, so

If \(\zeta(G)\geq C_r\), then \(\chi(G)\geq C_r\), hence

\(\delta(G)\geq r\). Take \(H=G\). This validates the live comment's direction.

(b; Alon–Krivelevich–Sudakov.) \(B_r\Rightarrow A_r\). Their Theorem 1.1

says that every graph of chromatic number \(m\) contains a subgraph \(H\) with

Choose \(C_r\) large enough that the right side of (2) is at least the

threshold \(Z_r\) from \(B_r\). Then \(H\) contains \(J\) with

\(\delta(J)\geq r\), and (1) gives \(\delta(G)\geq r\).

Thus, **under the standard containment convention, the two qualitative

questions are equivalent**. This is a clean reduction, not a solution: the

common assertion remains open.

2. Primary-source literature audit

I searched the exact conjecture name and statement, the cochromatic variant,

and 2024–2026 work on undirected dichromatic number. I opened the papers

rather than relying on search snippets.

• (b; source-verified.) In

Erdős, Problems and results in number theory and graph theory (1979), pp. 16–18,

Erdős reports the joint work with Neumann-Lara, defines the undirected

invariant as the worst orientation, and asks whether large chromatic number

forces large dichromatic number. The paper says they could not even prove

that sufficiently large chromatic number forces dichromatic number greater

than two.

• (b; metadata and live statement verified.) The second question is

attributed by the live page to

Erdős–Gimbel (1993)70393-5).

The DOI, title, authors, venue, and pages exist. The Elsevier full PDF

returned HTTP 403 in this environment, so I do not attribute any detailed

claim to it beyond the live page's authoritative statement and attribution.

• (b; source-verified.)

Alon, Krivelevich, and Sudakov, Subgraphs with a Large Cochromatic Number (1997),

Theorem 1.1, proves (2). This is the result recorded on live problem 760.

• (b; source-verified.)

Neumann-Lara, The 3 and 4-dichromatic tournaments of minimum order (1994)E0113-I)

proves that the minimum orders of 3- and 4-dichromatic tournaments are 7

and 11, respectively, and finds four nonisomorphic 3-dichromatic tournaments

of order 7. This is consistent with, but does not imply, the new

\(K_7-e\) computation below.

• (b; source-verified.)

Mohar and Wu, Dichromatic number and fractional chromatic number,

Forum of Mathematics, Sigma 4 (2016), e32, explicitly says that even the

existence of the threshold \(C_3\) is open. Its Theorem 1.3 proves the

fractional analogue

\[ \vec\chi_f(G)\geq \frac{t}{4\log_2(2et^2)} \quad\text{when }\chi_f(G)\geq t. \]

It also proves a quantitative positive result for Kneser graphs.

• (b; source-verified.)

Harutyunyan and Puig i Surroca, Colouring Complete Multipartite and Kneser-Type Digraphs,

EJC 32(3) (2025), #P3.1, still states the general conjecture as open.

Its Theorem 6 proves, for all sufficiently large \(n\) and

\(2\leq k\leq n/2\),

\[ \delta(KG(n,k))\geq \frac1{16}\chi(KG(n,k)). \]

• (b; source-verified and current.)

Harutyunyan, Picasarri-Arrieta, and Puig i Surroca, On the list version of a conjecture of Erdős and Neumann-Lara,

submitted 1 March 2026, again says it is unclear whether \(C_3\) exists.

It proves a list-colouring analogue, including an

\(\Omega(\log d)\) lower bound for the list dichromatic number of a suitable

orientation of every graph of minimum degree \(d\). This does not settle the

ordinary conjecture: a large list dichromatic number does not imply a large

ordinary dichromatic number.

(c; honest negative search.) I found no primary source claiming a proof or

counterexample to the general ordinary conjecture through the search date.

This negative search is not a proof of absence, but it agrees with the live

page and the March 2026 primary source.

3. New verified output: exact dichromatic number through order seven

Classification theorem

(d, with an elementary reduction.) For every nonempty finite simple graph

\(G\) with \(|V(G)|\leq7\),

Equivalently, the only underlying graphs of order at most seven with

dichromatic number three are \(K_7-e\) and \(K_7\).

In particular:

| Order \(n\) | Maximum possible \(\delta(G)\) |

|---:|---:|

| \(1,2\) | 1 |

| \(3,4,5,6\) | 2 |

| 7 | 3 |

Exhausted boundary graphs

The structural proof in Section 4 reduces (3) to the following small

exhaustions. The chromatic and cochromatic columns were recomputed by two

independent exact algorithms.

| Graph | \(m\) | \(\chi\) | \(\zeta\) | orientations exhausted | orientations with dicolouring number 3 |

|---|---:|---:|---:|---:|---:|

| \(K_6\) | 15 | 6 | 1 | 32,768 | 0 |

| \(K_7-\{01,02\}\) | 19 | 6 | 2 | 524,288 | 0 |

| \(K_7-\{01,23\}\) | 19 | 5 | 2 | 524,288 | 0 |

| \(K_7-\{01\}\) | 20 | 6 | 2 | 1,048,576 | 240 |

| \(K_7\) | 21 | 7 | 1 | not needed | at least one |

(d) The 240 bad orientations of \(K_7-e\) form one orbit under its

240-element automorphism group. Hence, up to isomorphism, there is exactly one

3-dichromatic orientation of \(K_7-e\). It is the explicit orientation in

Section 5. It is arc-critical: deleting any one of its 20 arcs makes it

2-dicolourable.

4. Why the finite classification follows from those computations

Dichromatic number one

(a) \(\delta(G)=1\) if and only if \(G\) is a forest. If \(G\) is a forest,

no orientation has a directed cycle. Conversely, if \(G\) has an undirected

cycle, orient that cycle consistently and orient all remaining edges

arbitrarily. The resulting orientation is not 1-dicolourable.

Universal upper bound at order seven

(a) Every orientation of every seven-vertex graph is 3-dicolourable.

There is always an acyclic triple:

• if the underlying graph is incomplete, take a nonadjacent pair and any

third vertex; the induced triple has at most two arcs and cannot contain a

directed cycle;

• if it is complete, choose a vertex of the tournament and two of its

out-neighbours or two of its in-neighbours. Such two neighbours exist, and

the chosen vertex is a source or sink in the triple.

Use that triple as one colour and split the remaining four vertices into two

pairs. Each pair is acyclic.

Sparse seven-vertex graphs

(a) Every graph on at most six vertices is a subgraph of \(K_6\).

The exhaustive \(K_6\) certificate and monotonicity (1) therefore give

\(\delta(G)\leq2\) through order six.

Now let \(G\) have seven vertices and at most 19 edges. It has at least two

nonedges. Any two edges of \(K_7\) are either adjacent or disjoint, so after a

relabeling,

The verifier independently generates the two relabeling orbits: each has 105

unordered edge pairs and together they are all

\(\binom{21}{2}=210\) pairs. The exhaustive certificates for the two

19-edge supergraphs and (1) give \(\delta(G)\leq2\).

Dense seven-vertex graphs

(a+d) A seven-vertex graph with at least 20 edges is \(K_7-e\) or \(K_7\).

Section 5 gives an orientation of \(K_7-e\) requiring three colours, so

monotonicity gives the same lower bound for \(K_7\). The universal upper bound

above gives equality. Combining this with the cycle lower bound proves (3).

5. Explicit \(K_7-e\) orientation and certificate

Let the vertices be \(0,\ldots,6\), omit the edge \(01\), and orient every

other edge by the following out-neighbour lists:

| \(v\) | \(N_D^+(v)\) |

|---:|---|

| 0 | \(2,5\) |

| 1 | \(2,3,4\) |

| 2 | \(3,4,5\) |

| 3 | \(0,4,6\) |

| 4 | \(0,5,6\) |

| 5 | \(1,3,6\) |

| 6 | \(0,1,2\) |

Equivalently, the 20 arcs are

where \(uv\) means \(u\to v\).

(d; exhaustive finite certificate.) Its twelve directed triangles, written

in cyclic order, are

These triangles certify cyclicity of 31 of the 35 four-vertex sets. The only

four acyclic four-sets are:

| Acyclic set | A topological order | Directed cycle in its complement |

|---|---|---|

| \(\{0,1,2,6\}\) | \(6,0,1,2\) | \(3\to4\to5\to3\) |

| \(\{0,1,3,4\}\) | \(1,3,4,0\) | \(2\to5\to6\to2\) |

| \(\{0,3,4,6\}\) | \(3,4,6,0\) | \(1\to2\to5\to1\) |

| \(\{1,2,3,4\}\) | \(1,2,3,4\) | \(0\to5\to6\to0\) |

There is no acyclic set of size at least five: such a five-set would contain

five distinct acyclic four-subsets, while the displayed list has only four.

In a putative 2-dicolouring, one colour class has at least four vertices. If

it is acyclic, it must be one of the four displayed sets, but its complement

contains the displayed directed triangle. Therefore no 2-dicolouring exists.

On the other hand,

is a 3-dicolouring. Thus this orientation has dicolouring number exactly

three.

The verifier checks all 64 unordered bipartitions using two independent cycle

tests, rather than trusting only the compact certificate above.

6. Standalone verification

Run:

python runs/erdos761_wave6l_verify.py

The script uses only the Python standard library and does not load a graph

atlas or saved certificate. It:

1. generates \(K_6\), the two 19-edge boundary graphs, and \(K_7-e\);

2. exhausts orientations in Gray-code order;

3. directly reconstructs every orientation to cross-check the Gray update;

4. searches all 32 or 64 unordered bipartitions with a Kahn source-deletion

acyclicity test;

5. validates every positive colouring certificate with an independent DFS

recursion-stack cycle detector;

6. validates every negative \(K_7-e\) orientation by an independent DFS

exhaustion of all 64 bipartitions;

7. constructs the full relabeling orbit of the explicit witness;

8. verifies its triangles, acyclic four-sets, complementary cycles,

3-dicolouring, and a 2-dicolouring after each arc deletion;

9. recomputes \(\chi\) and \(\zeta\) both by subset DP and independent

set-partition backtracking; and

10. checks the adjacent/disjoint two-nonedge orbit reduction under all

\(7!\) vertex relabelings.

(d) A fresh run checked 2,129,920 orientations and ended in PASS.

The deterministic certificate hashes were:

| Stream | SHA-256 |

|---|---|

| \(K_6\) selected 2-dicolourings | f8ced591e7cee9e43fb4e303aaf7d13ffaf7b685244edb28ba8f2669330c5cd9 |

| adjacent-two-nonedges selected 2-dicolourings | bd48c017015a5057db0086bd8ac140e54bbb0b27ee7ab3f1c1e693cc71694f8b |

| disjoint-two-nonedges selected 2-dicolourings | 68b5f7d97b73e08400d50789e90975c91f66f8fbf3a62d37a17e7cafb1ae07a9 |

| all \(K_7-e\) outcomes | 5ce196f0e12f3e47633456a20c862c5bfcda0e48cf5465890f3bb24de083dfe4 |

| sorted 3-dichromatic \(K_7-e\) masks | cfb3f6ee91a73600c49d8c6ef5656968dbde8c9b2ae8208523074ed1c849a538 |

The explicit witness has orientation mask 41750 when the edges of

\(K_7-\{01\}\) are lexicographically ordered and bit 0 means low endpoint to

high endpoint.

7. Exact wall

The first unknown threshold is already

Equivalently, is there a finite \(C\) such that every graph of chromatic

number at least \(C\) has an orientation whose directed-cycle hypergraph is

not 2-colourable? The 2016, 2025, and March 2026 primary sources all identify

(4) as open.

The principal standard routes stop for precise reasons:

• Fractional route. Mohar–Wu needs large \(\chi_f(G)\), but large

\(\chi(G)\) does not force large \(\chi_f(G)\). They explicitly treat Kneser

graphs whose fractional chromatic number stays below \(2+\varepsilon\)

while their chromatic number grows. Special Kneser structure still gives

large dichromatic number, but the fractional theorem alone cannot use the

hypothesis of (4).

• List route. The March 2026 theorem forces large list dichromatic

number from large list chromatic number. Since list dichromatic number may

exceed ordinary dichromatic number, it supplies no lower bound of the

needed type for ordinary \(\delta(G)\).

• Tournament route. Complete graphs and tournaments have strong

\(\Theta(n/\log n)\) theory, but graphs of arbitrarily large chromatic

number need not contain large cliques. Completing missing edges changes the

underlying graph and does not transfer a tournament lower bound back after

deletions.

(c) The exact missing lemma is therefore not another order-seven case:

it is a uniform mechanism converting large ordinary chromatic number into one

orientation for which every vertex bipartition has a directed cycle on one

side.

Cost of the next naive finite census

(d; diagnostic only.) nauty-geng -q 8 produces 12,346 unlabeled

eight-vertex graphs. Summing \(2^{e(G)}\) over them gives 2,496,391,267

orientation instances. The robust verifier above sustained about 61,600

orientation instances per second, so a naive order-eight repetition would

cost about 11.3 core-hours, roughly USD 0.6–1.1 at USD 0.05–0.10 per

core-hour. I did not run it. SAT plus isomorphism/monotonicity pruning should

reduce that cost substantially, but even a complete order-eight census would

not provide the uniformity required in (4).

PARTIAL: 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-e\) and \(K_7\) have dichromatic number \(3\), with a unique explicit 3-dichromatic orientation of \(K_7-e\) up to isomorphism.