In-dominating-set conjecture for digraphs of large outdegree

About 6 years old · traced to

For a digraph DD, let δ+(D)\delta^+(D) be its minimum out-degree. A set X⊆V(D)X\subseteq V(D) is in-dominating if every vertex in V(D)∖XV(D)\setminus X has an out-neighbor in XX.

In-dominating-set conjecture. There exists a function f:N→Nf:\mathbb{N}\rightarrow\mathbb{N} such that, for every k≥1k\geq1, if

δ+(D)≥f(k),\delta^+(D)\geq f(k),

then there is an in-dominating set X⊊V(D)X\subsetneq V(D) satisfying δ+(D−X)≥k\delta^+(D-X)\geq k.

The source presents this as a natural statement that would imply the out-leaf extension conjecture; its resolution is not stated in the supplied text.

References

Primary source

Lior Gishboliner, Raphael Steiner and Tibor Szabó, “Oriented cycles in digraphs of large outdegree”, arXiv:2008.13224 (2020).

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.