# Quasi-kernels and quasi-sinks

A **quasi-kernel** of a digraph [math]D[/math] is an independent vertex set [math]K[/math] sucht that every vertex is reachable from [math]K[/math] in [math]D[/math] by a path of length at most two. A **quasi-sink** of [math]D[/math] is a quasi-kernel of the digraph that we obtain by changing the direction of the edges in [math]D[/math]. Is it true that for any infinite digraph [math]D=(V,A)[/math] there is a partition [math]\{V_1, V_2\}[/math] of [math]V[/math] such that [math]D[V_1][/math] admits a quasi-kernel and [math]D[V_2][/math] admits a quasi-sink?

## Remarks

V. Chvátal and L. Lovász proved that every finite digraph has a quasi-kernel ^{[1]}. This is not true for infinite digraphs, take for example [math]V=\mathbb{Z}[/math] and let [math](m,n)\in A [/math] iff [math]m\ltn[/math]. P. L. Erdős, A. Hajnal, L. Soukup showed that in any infinite digraph, one can find disjoint independent sets [math]S, T[/math] such that for every vertex [math]v[/math] there is a path [math]P[/math] of length at most two such that [math]P[/math] either goes from [math]S[/math] to [math]v[/math] or from [math]v[/math] to [math]T[/math] (^{[2]} p. 3041. Theorem 2.1).

## References

- ↑ V. Chvátal and L. Lovász.
*Every directed graph has a semi-kernel.*Hypergraph Seminar. Springer Berlin Heidelberg, 1974, DOI link - ↑ P. L. Erdős and L. Soukup.
*Quasi-kernels and quasi-sinks in infinite graphs.*Discrete mathematics 309.10 (2009): 3040-3048. DOI link, arXiv link