Erdős–Soukup partition conjecture for quasi-kernels and quasi-sinks
Erdős–Soukup partition conjecture for quasi-kernels and quasi-sinks
Let be a digraph. An independent set is a quasi-kernel if every vertex of can be reached from some vertex of by a directed path of length at most ; dually, is a quasi-sink if every vertex can reach some vertex of by a directed path of length at most . For , write for the subgraph induced by .
Erdős–Soukup's conjecture. Every digraph has a partition such that has a quasi-kernel and 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.