Quasi-kernels and quasi-sinks

From Egres Open
Jump to: navigation, search

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

  1. V. Chvátal and L. Lovász. Every directed graph has a semi-kernel. Hypergraph Seminar. Springer Berlin Heidelberg, 1974, DOI link
  2. 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