Alon's partition conjecture for digraphs

Let DD be a digraph, let DViD\langle V_i\rangle denote the subdigraph induced by ViV_i, and let kk be a positive integer. Alon's partition conjecture. There exists a function hh such that every digraph with minimum out-degree at least h(k)h(k) has a partition (V1,V2)(V_1,V_2) for which each DViD\langle V_i\rangle, i=1,2i=1,2, has minimum out-degree at least kk. The source says that even the existence of h(2)h(2) remains open; if true, the conjecture would imply closure of the class of δ+\delta^+-maderian digraphs under disjoint union.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Nathann Cohen, Fréderic Havet, William Lochet, Phablo F. S. Moura and Stéphan Thomassé, “Subdivisions in digraphs of large out-degree or large dichromatic number”, arXiv:1610.00876 (2016).

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.