Erdős–Soukup partition conjecture for quasi-kernels and quasi-sinks

Let G=(V,E)G=(V,E) be a digraph. An independent set AVA\subset V is a quasi-kernel if every vertex of GG can be reached from some vertex of AA by a directed path of length at most 22; dually, AA is a quasi-sink if every vertex can reach some vertex of AA by a directed path of length at most 22. For WVW\subset V, write G[W]G[W] for the subgraph induced by WW.

Erdős–Soukup's conjecture. Every digraph G=(V,E)G=(V,E) has a partition (V0,V1)(V_0,V_1) such that G[V0]G[V_0] has a quasi-kernel and G[V1]G[V_1] has a quasi-sink.

The finite analogue, that every finite digraph has a quasi-kernel, is due to Chvátal and Lovász, whereas the direct assertion fails for infinite digraphs, even for tournaments. The conjecture asks whether a simultaneous quasi-kernel/quasi-sink partition always exists.

Sources & referencesView supporting material

Primary source

Peter L. Erdos and Lajos Soukup, “Quasi-kernels and quasi-sinks in infinite graphs”, arXiv:0712.0663 (2007).

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.