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:

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.

(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:

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:

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;

1. validates every positive colouring certificate with an independent DFS

recursion-stack cycle detector;

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

exhaustion of all 64 bipartitions;

1. constructs the full relabeling orbit of the explicit witness;
2. verifies its triangles, acyclic four-sets, complementary cycles,

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

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

set-partition backtracking; and

1. 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:

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.