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

About 3 years old · traced to

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)=A∪BV(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.

References

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).

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.