The directed-clique conjecture for the minimum degree of digraphs

About 2 years old · traced to

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.

References

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.