The directed-clique conjecture for the minimum degree of digraphs

Let DD be a digraph, and let Δmin(D)\Delta_{\min}(D) denote its minimum degree parameter as defined in the paper. Let χ(D)\vec\chi(D) be its dichromatic number. A directed clique is a vertex set XX that can be partitioned into (X1,X2)(X_1,X_2) such that both D[X1]D[X_1] and D[X2]D[X_2] are complete digraphs and every possible arc from X1X_1 to X2X_2 is present. Let ω(D)\vec\omega(D) be the maximum size of a directed clique in DD.

Directed-clique conjecture. There exists ε>0\varepsilon>0 such that every digraph DD satisfies

χ(D)(1ε)Δmin(D)+εω(D).\vec\chi(D)\leq\left\lceil(1-\varepsilon)\Delta_{\min}(D)+\varepsilon\vec\omega(D)\right\rceil.

The conjecture is proposed after a related bound using the biclique number is shown to fail for Δmin\Delta_{\min}. It is presented as an open strengthening of the paper's partial result with Δ~\widetilde{\Delta}; no resolution is given.

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.