Erdős, Péter L.; Soukup, Lajos Quasi-kernels and quasi-sinks in infinite graphs. (English) Zbl 1208.05033 Discrete Math. 309, No. 10, 3040-3048 (2009). Summary: Given a directed graph \(G=(V,E)\) an independent set \(A\subset V\) is called quasi-kernel (quasi-sink) iff for each point \(v\) there is a path of length at most 2 from some point of \(A\) to \(v\) (from \(v\) to some point of \(A\)). Every finite directed graph has a quasi-kernel. The plain generalization for infinite graphs fails, even for tournaments. We study the following conjecture: for any digraph \(G=(V,E)\) there is a partition \((V_{0},V_{1})\) of the vertex set such that the induced subgraph \(G[V_{0}]\) has a quasi-kernel and the induced subgraph \(G[V_{1}]\) has a quasi-sink. Cited in 3 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C63 Infinite graphs Keywords:infinite directed graph; quasi-kernel; quasi-sink PDFBibTeX XMLCite \textit{P. L. Erdős} and \textit{L. Soukup}, Discrete Math. 309, No. 10, 3040--3048 (2009; Zbl 1208.05033) Full Text: DOI arXiv References: [1] Chvátal, V.; Lovász, L., Every directed graph has a semi-kernel, Lecture Notes Math., 411, 175 (1974) · Zbl 0297.05116 [2] Galeana-Sánchez, H.; Li, Xueliang, Semikernels and \((k, l)\)-kernels in digraphs, SIAM J. Discrete Math., 11, 340-346 (1998) · Zbl 0907.05025 [3] Gutin, G.; Koh, K. M.; Tay, E. G.; Yao, A., On the number of quasi-kernels in digraphs, J. Graph Theory, 46, 48-56 (2004) · Zbl 1051.05046 [4] Jacob, H.; Meyniel, H., About quasi-kernels in a digraph, Discrete Math., 154, 279-280 (1996) · Zbl 0854.05055 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.