Erdős Problem #761

Problem 761 (Round 2)

1) ROUND-2 OBJECTIVE

I pursue (C) obstruction/correction. A full proof or counterexample is still out of reach, but Round 1 left two decisive gaps that can now be closed rigorously:

1. the relation between the two questions (large chromatic number versus large cochromatic number), and
2. the lack of any unconditional lower bound on $\delta(G)$ in terms of $\chi(G)$ beyond the trivial $\delta(G)\le \chi(G)$.

The most promising Round-2 step is therefore to isolate the exact structural obstruction by proving the right monotonicity statements, showing that the two formulations are equivalent up to a parameter transfer, and importing the best currently verified quantitative lower bound.

2) Round-1 FOUNDATION USED

I use the following Round-1 ingredients.

• For every graph $G$, one has $1\le \delta(G)\le \chi(G)$.
• The Erdős--Neumann-Lara conjecture (Question Q1) was identified correctly as open.
• The Alon--Krivelevich--Sudakov theorem was already cited in Round 1: large chromatic number forces a subgraph of cochromatic number $\Omega(\chi/\log\chi)$.
• The fractional result of Mohar--Wu was already cited in Round 1.

3) NEW INSIGHT / TOOL (ROUND-2)

Round 2 adds four concrete advances.

1. (i) Subgraph monotonicity of $\delta$. If $H\subseteq G$, then $\delta(H)\le \delta(G)$.
2. (ii) Equivalence of the two Erdős questions up to parameter transfer. Since $\zeta(G)\le \chi(G)$, Question Q1 immediately implies Question Q2 by taking $H=G$. Conversely, the Alon--Krivelevich--Sudakov theorem converts Question Q2 back into Question Q1.
3. (iii) A genuine quantitative lower bound. Aboulker, Havet, Pirot and Schabanel proved that every $n$-vertex graph satisfies \[ \chi(G)\le 2\delta(G)\left(1+\lfloor\log_2 n\rfloor\right). \] Equivalently, \[ \delta(G)\ge \frac{\chi(G)}{2(1+\lfloor\log_2 |V(G)|\rfloor)}. \] This does not settle the conjecture, but it rules out any counterexample family whose order is too small relative to its chromatic number.
4. (iv) List-analogue evidence. In 2026, Harutyunyan, Picasarri-Arrieta and Puig i Surroca proved the list analogue \[ \vec\chi_\ell(G)\ge \left(\frac13-o(1)\right)\log_2 \chi_\ell(G), \] which is substantial adjacent evidence even though it does not settle the original parameter $\delta(G)$.

4) ATTACK PLAN (ROUND-2)

The precise Round-1 gaps were:

• Round 1 only explained one implication between Q1 and Q2; the reverse implication and the monotonicity needed for it were not made explicit.
• Round 1 recorded fractional evidence but no unconditional inequality forcing $\delta(G)$ to grow with $\chi(G)$ under an additional hypothesis.

I therefore prove the missing monotonicity lemma, deduce the equivalence of Q1 and Q2 (up to a logarithmic loss through the AKS theorem), and then apply the 2025 theorem \[ \chi(G)\le 2\delta(G)(1+\lfloor\log_2 |V(G)|\rfloor) \] to obtain a sharp obstruction to bounded-dichromatic counterexamples.

5) WORK (ROUND-2)

Recall that $\delta(G)$ denotes the maximum dichromatic number over all orientations of $G$.

Lemma 5.1 (subgraph monotonicity).

If $H\subseteq G$, then \[ \delta(H)\le \delta(G). \]

Proof. Choose an orientation $D_H$ of $H$ with $\chi_d(D_H)=\delta(H)$. Extend $D_H$ arbitrarily to an orientation $D_G$ of $G$. Any dicolouring of $D_G$ restricts to a dicolouring of $D_H$, so \[ \chi_d(D_H)\le \chi_d(D_G)\le \delta(G). \] Therefore $\delta(H)=\chi_d(D_H)\le \delta(G)$. $\square$

Proposition 5.2.

A positive answer to Question Q1 implies a positive answer to Question Q2.

Proof. Suppose Q1 holds: there exists a function $f$ such that $\chi(G)\ge f(k)$ implies $\delta(G)\ge k$. Since every graph satisfies $\zeta(G)\le \chi(G)$, the implication \[ \zeta(G)\ge f(k)\implies \chi(G)\ge f(k)\implies \delta(G)\ge k \] shows that Q2 holds, taking $H=G$. $\square$

Proposition 5.3.

A positive answer to Question Q2 implies a positive answer to Question Q1.

Proof. Assume Q2 holds, so there exists a function $g$ such that \[ \zeta(J)\ge g(k)\implies \exists H\subseteq J \text{ with } \delta(H)\ge k. \] Let $G$ be a graph with chromatic number $m$. By the Alon--Krivelevich--Sudakov theorem, $G$ contains a subgraph $J\subseteq G$ with \[ \zeta(J)\ge c\,\frac{m}{\log m} \] for some absolute constant $c>0$ and all large enough $m$. Choose $m$ so large that \[ c\,\frac{m}{\log m}\ge g(k). \] Then Q2 gives a subgraph $H\subseteq J\subseteq G$ with $\delta(H)\ge k$. By Lemma 5.1, \[ \delta(G)\ge \delta(H)\ge k. \] Hence large chromatic number forces large dichromatic number, i.e. Q1 holds. $\square$

Conclusion from Propositions 5.2 and 5.3.

The two questions in Problem 761 are qualitatively equivalent: Q1 trivially implies Q2, while Q2 implies Q1 via the AKS subgraph theorem.

External theorem used.

(Aboulker--Havet--Pirot--Schabanel.) Every graph $G$ of order $n$ satisfies \[ \chi(G)\le 2\delta(G)\left(1+\lfloor\log_2 n\rfloor\right). \]

Corollary 5.4.

Every graph $G$ satisfies \[ \delta(G)\ge \frac{\chi(G)}{2(1+\lfloor\log_2 |V(G)|\rfloor)}. \] In particular, if \[ \chi(G)>2(k-1)(1+\lfloor\log_2 |V(G)|\rfloor), \] then $\delta(G)\ge k$.

Proof. This is just a rearrangement of the theorem. $\square$

Corollary 5.5 (exponential-size obstruction).

Fix $D\in\mathbb N$. If $\delta(G)\le D$, then \[ |V(G)|\ge 2^{\chi(G)/(2D)-1}. \]

Proof. From Corollary 5.4, \[ \chi(G)\le 2D(1+\lfloor\log_2 |V(G)|\rfloor)\le 2D(1+\log_2 |V(G)|). \] Hence \[ \log_2 |V(G)|\ge \frac{\chi(G)}{2D}-1, \] which is equivalent to the displayed bound. $\square$

What this means for the original conjecture.

Any family $\{G_t\}$ with bounded dichromatic number and unbounded chromatic number must necessarily have order at least exponential in $\chi(G_t)$. Thus one entire class of possible counterexamples is ruled out: no counterexample family can have $|V(G_t)|=\exp(o(\chi(G_t)))$.

6) ADVERSARIAL VERIFICATION

• Monotonicity check. In Lemma 5.1, extending an orientation from $H$ to $G$ is harmless because every dicolouring of the larger oriented graph restricts to a dicolouring of the smaller one.
• Q1 $\Rightarrow$ Q2 check. This uses only the elementary inequality $\zeta(G)\le \chi(G)$ and is therefore immediate.
• Q2 $\Rightarrow$ Q1 check. The only nontrivial input is the AKS theorem. After obtaining $H\subseteq G$ with large $\delta(H)$, Lemma 5.1 is exactly what transfers the conclusion back to $G$.
• Quantifier check. The equivalence of Q1 and Q2 is only at the level of existence of some forcing function; the actual functions differ because the AKS step loses a logarithm.
• Why the list result does not solve the problem. Large list dichromatic number does not force equally large ordinary dichromatic number for the same orientation, so the 2026 list theorem is genuine evidence, not a solution to Q1.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED). Round 2 proves a genuine structural reduction not present in Round 1:

1. the two questions in Problem 761 are equivalent up to a parameter transfer, and
2. every graph satisfies the unconditional lower bound \[ \delta(G)\ge \frac{\chi(G)}{2(1+\lfloor\log_2 |V(G)|\rfloor)}. \] Thus any bounded-$\delta$ counterexample family must have exponentially large order in its chromatic number. The list analogue is now settled, which further narrows the gap.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%

9) REFERENCES

• B. Mohar and H. Wu, Dichromatic number and fractional chromatic number, Forum Math. Sigma 4 $2016$, e32.
• N. Alon, M. Krivelevich, and B. Sudakov, Subgraphs with a large cochromatic number, J. Graph Theory 26 $1997$, 295--297.
• P. Aboulker, F. Havet, F. Pirot, and J. Schabanel, Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order, Electron. J. Combin. 32$4$ $2025$, Paper P4.27.
• A. Harutyunyan, L. Picasarri-Arrieta, and G. Puig i Surroca, On the list version of a conjecture of Erdős and Neumann-Lara, arXiv:2603.01020, 2026.

10) OUTPUT FORMAT

Here the Erdős problem number is $x=761$.

OBJECTIVE AND SOURCE REVIEW

Erdős #761; independent attempt, 2026-09-23. Write $\delta(G)$ for the maximum dichromatic number of an orientation of $G$, and $\zeta(G)$ for its cochromatic number. Must unbounded chromatic number force unbounded $\delta$? Must large $\zeta$ force a subgraph of large $\delta$? I read the complete 761.tex, including its equivalence argument, order-dependent bound, and distinction between list and ordinary dichromatic numbers. Those results do not remove the dependence on graph order in the original question.

WORK: AN ELEMENTARY CLIQUE-SIZE SPECIAL CASE

For $m\ge2$, put $k=\lceil2\log_2m+2\rceil$. Orient $K_m$ randomly and independently. On any specified $k$ vertices, an acyclic tournament is transitive and has a unique linear order, so at most $k!$ of the $2^{\binom{k}{2}}$ orientations are acyclic. The expected number of acyclic $k$-sets is at most \[ \binom mk k!2^{-\binom{k}{2}} \le m^k2^{-k(k-1)/2}<1. \] If $k>m$ the count is zero directly. Hence some orientation has no acyclic $k$-set, and every acyclic colour class has at most $k-1$ vertices. Therefore \[ \delta(K_m)\ge\left\lceil\frac{m}{\lceil2\log_2m+2\rceil-1}\right\rceil. \] The only structural fact used is elementary: a finite acyclic digraph has a source, and deleting sources orders all its vertices; in a tournament every edge must follow that order. If $G$ contains $K_m$, extend this orientation arbitrarily to its other edges. Any acyclic colouring of the resulting orientation restricts to one of the clique, proving the same lower bound for $\delta(G)$. This rederives a classical probabilistic special case without relying on a list-colouring theorem.

ADVERSARIAL VERIFICATION AND REMAINING GAP

The estimate uses the largest clique, not the chromatic number. Graphs of bounded clique number can have arbitrarily large chromatic number, so this does not settle the first question. In particular, replacing $m=\omega(G)$ by $\chi(G)$ in the displayed proof would be invalid: the induced orientation on a general vertex subset need not be a tournament. For the cochromatic question, the elementary implication $\zeta(G)\le\chi(G)$ would transfer a positive answer to the first question, but the first question remains unproved. No improvement to the supplied general bound is claimed.

SOURCES CHECKED

The complete local 761.tex; official indexed statement under https://www.erdosproblems.com/tags/chromatic%20number/open. The counting proof above is self-contained and is not claimed novel.

FINAL

UNRESOLVED. A uniform lower bound in terms of clique size is verified; both unrestricted questions remain.

COMPLETION ESTIMATE

Conservative subjective progress toward the unrestricted questions. COMPLETION: 8%

Problem 761

1) FORMAL RESTATEMENT

For a graph $G$:

• The chromatic number $\chi(G)$ is the minimum $m$ such that $V(G)$ can be partitioned into $m$ independent sets.
• The cochromatic number $\zeta(G)$ is the minimum $m$ such that $V(G)$ can be partitioned into $m$ parts, where each part induces either a clique or an independent set.
• For an orientation $D$ of $G$ (replace each undirected edge by one of the two possible directions), let $\chi_d(D)$ be the minimum number of colours needed to colour $V(D)$ so that each colour class induces an acyclic digraph (equivalently: contains no directed cycle). This is the standard dichromatic number of $D$.
• Define the (undirected) dichromatic number of $G$ as \[ \delta(G):=\max\{\chi_d(D): D\ \text{is an orientation of }G\}. \]

The questions are:

1. $Q1$ Does $\chi(G)$ unbounded force $\delta(G)$ unbounded? Equivalently: for every $k$ does there exist $f(k)$ so that $\chi(G)\ge f(k)$ implies $\delta(G)\ge k$?
2. $Q2$ Does $\zeta(G)$ large force the existence of a (not necessarily induced) subgraph $H\subseteq G$ with large $\delta(H)$?

2) QUICK LITERATURE/CONTEXT CHECK

The first question is widely known as the Erdős--Neumann-Lara conjecture. A key reference is Mohar--Wu, Dichromatic number and fractional chromatic number (arXiv:1510.05982), which states the conjecture and notes that even the case $k=3$ remains open. They prove a fractional version: large fractional chromatic number forces large fractional dichromatic number.

The second question is attributed to Erdős--Gimbel in the same source list. A known result of Alon--Krivelevich--Sudakov $1997$ shows that large $\chi(G)$ forces the presence of a subgraph with large $\zeta(\cdot)$ (in the order $\gg \chi/\log\chi$); hence a positive answer to $Q2$ would imply a positive answer to $Q1$.

3) ATTACK PLAN

For $Q1$ one can try to:

• prove quantitative lower bounds on $\delta(G)$ in terms of graph parameters that are forced by large $\chi(G)$ (e.g. density, expansion, fractional chromatic number), or
• construct a counterexample family with $\chi(G)\to\infty$ but with every orientation $k$-dicolourable for fixed $k$.

Mohar--Wu suggest that the fractional version may be a stepping stone: if one could control $\chi_f$ from below by $\chi$ within a large class of graphs, then one would obtain partial confirmations.

For $Q2$, one may try to show: if $\zeta(G)$ is large, then $G$ contains a subgraph $H$ with large $\chi_f(H)$, then appeal to the fractional dichromatic lower bounds.

4) WORK

Basic observations.

• Always $1\le \delta(G)\le \chi(G)$. Indeed, for any orientation $D$ a proper $\chi(G)$-colouring makes every colour class an independent set, hence acyclic.
• If $G$ is a forest then $\delta(G)=1$ (every orientation is acyclic). If $G$ contains a cycle, then $\delta(G)\ge 2$ (orient that cycle cyclically). Hence the threshold for guaranteeing $\delta(G)\ge 2$ is $\chi(G)\ge 3$ (since $\chi\le 2$ graphs can be forests).
• For a complete graph $K_n$, $\delta(K_n)$ equals the maximum dichromatic number of an $n$-vertex tournament. Known results on tournaments show this grows unboundedly with $n$ (on the order $\Theta(n/\log n)$ up to constants), so $\chi(K_n)=n$ does force $\delta(K_n)\to\infty$.

Fractional evidence (Mohar--Wu).

Let $\chi_f(G)$ denote the fractional chromatic number of $G$. Mohar--Wu prove that if $\chi_f(G)\ge t$, then the fractional dichromatic number of $G$ satisfies \[ \delta_f(G)\ \gtrsim\ \frac{t}{\log t}. \] Since $\delta(G)\ge \delta_f(G)$, this yields a (logarithmically weakened) implication "large $\chi_f$ $\Rightarrow$ large $\delta$". This does not settle $Q1$ because $\chi_f$ can be much smaller than $\chi$ in some graphs.

Link between $Q2$ and $Q1$.

If $Q2$ had a positive answer of the form \[\zeta(G)\ge g(k)\ \Rightarrow\ \exists H\subseteq G\ \text{with }\delta(H)\ge k,\] then combining with the Alon--Krivelevich--Sudakov theorem that large $\chi(G)$ forces a subgraph with $\zeta$ on the order $\chi/\log\chi$ would imply $Q1$.

5) OBSTRUCTIONS/CAVEATS

• The key open difficulty in $Q1$ is already at $k=3$: it is unknown whether there exist graphs with arbitrarily large chromatic number whose every orientation is $2$-dicolourable.
• For $Q2$, even translating "large $\zeta$" into "large $\chi_f$ on some subgraph" is nontrivial; $\zeta$ mixes cliques and independent sets.

6) FINAL

UNRESOLVED.

• (i) Where I got stuck: I did not prove a general implication $\chi(G)\to\infty\Rightarrow \delta(G)\to\infty$ nor construct a counterexample.
• (ii) Partial progress: I recorded standard reductions and verified the easy threshold for $\delta\ge 2$, and explained how fractional results (Mohar--Wu) and the AKS subgraph theorem connect to the questions.
• (iii) What seems next: Either (a) build a family with bounded $\delta$ but unbounded $\chi$ by controlling all orientations, or (b) strengthen Mohar--Wu-type arguments to integral dichromatic number (or show that large $\chi$ forces large $\chi_f$ inside a subgraph with structure forcing large $\delta$).
• (iv) Best guess: The conjecture is true but difficult; available evidence is consistent with at least polylogarithmic growth.

7) COMPLETION ESTIMATE

$15\%$.