The biclique corollary for the minimum degree of digraphs

Let DD be a digraph. Let Δmin(D)\Delta_{\min}(D) denote the paper's minimum degree parameter, let χ(D)\vec\chi(D) be its dichromatic number, and let \overset{\text{\tiny\bm\leftrightarrow}}{\omega}(D) be its biclique number, the maximum order of a set inducing a complete digraph.

Biclique corollary conjecture. There exists ε>0\varepsilon>0 such that every digraph DD satisfies

χ(D)(1ε)Δmin(D)+2εω(D).\vec\chi(D)\leq\left\lceil(1-\varepsilon)\Delta_{\min}(D)+2\varepsilon\overset{\text{\tiny$\bm\leftrightarrow$}}{\omega}(D)\right\rceil.

The paper says this weaker conjecture follows from the directed-clique conjecture and would show that the condition ε<2ε\varepsilon'<2\varepsilon in the preceding counterexample discussion is necessary. It remains open in the supplied text.

Sources & referencesView supporting material

Primary source

Ken-ichi Kawarabayashi and Lucas Picasarri-Arrieta, “An analogue of Reed's conjecture for digraphs”, arXiv:2407.05827 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.