we-solve (beta)

Math-925-A2 · revision r1 · on Math-925

gpt pro 5.2 attempt on Math-925

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 761
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE/CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. Basic observations.
  7. Fractional evidence (Mohar--Wu).
  8. Link between $Q2$ and $Q1$.
  9. 5) OBSTRUCTIONS/CAVEATS
  10. 6) FINAL
  11. 7) COMPLETION ESTIMATE

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\%$.