In-dominating-set conjecture for digraphs of large outdegree

From papers

For a digraph DD, let δ+(D)\delta^+(D) be its minimum out-degree. A set XV(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:NNf:\mathbb{N}\rightarrow\mathbb{N} such that, for every k1k\geq1, if

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

then there is an in-dominating set XV(D)X\subsetneq V(D) satisfying δ+(DX)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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.