Erdős–Hajnal–Soukup partition conjecture for infinite digraphs
Erdős–Hajnal–Soukup partition conjecture for infinite digraphs
Let be a countably infinite directed graph. For an independent vertex set , call a quasi-sink if every vertex lies at directed distance at most two into , and call an independent vertex set a quasi-kernel if every vertex lies at directed distance at most two out of .
Erdős–Hajnal–Soukup partition conjecture. There is a partition
such that contains a quasi-sink and 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
Sign in to submit a solution.
No solutions have been posted yet.