Erdős–Hajnal–Soukup partition conjecture for infinite digraphs

From papers

Let GG be a countably infinite directed graph. For an independent vertex set KK, call KK a quasi-sink if every vertex lies at directed distance at most two into KK, and call an independent vertex set QQ a quasi-kernel if every vertex lies at directed distance at most two out of QQ.

Erdős–Hajnal–Soukup partition conjecture. There is a partition

V(G)=ABV(G)=A\cup B

such that G[A]G[A] contains a quasi-sink and G[B]G[B] contains a quasi-kernel.

This is proposed as a genuine infinite analogue of the Chvátal–Lovász quasi-kernel theorem. The supplied text gives no resolution.

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

Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei, Nika Salia and Mykhaylo Tyomkyn, “On the Small Quasi-kernel conjecture”, arXiv:2307.04112 (2024).

Solutions 0

No solutions have been posted yet.