# Towards the Small Quasi-Kernel Conjecture

@article{Kostochka2020TowardsTS, title={Towards the Small Quasi-Kernel Conjecture}, author={Alexandr V. Kostochka and Ruth Luo and Songling Shan}, journal={arXiv: Combinatorics}, year={2020} }

Let $D=(V,A)$ be a digraph. A vertex set $K\subseteq V$ is a quasi-kernel of $D$ if $K$ is an independent set in $D$ and for every vertex $v\in V\setminus K$, $v$ is at most distance 2 from $K$. In 1974, Chv\'atal and Lov\'asz proved that every digraph has a quasi-kernel. P. L. Erd\H{o}s and L. A. Sz\'ekely in 1976 conjectured that if every vertex of $D$ has a positive indegree, then $D$ has a quasi-kernel of size at most $|V|/2$. This conjecture is only confirmed for narrow classes of digraphs… Expand

#### 4 Citations

Kernels and Small Quasi-Kernels in Digraphs

- Mathematics
- 2021

A directed graph $D=(V(D),A(D))$ has a kernel if there exists an independent set $K\subseteq V(D)$ such that every vertex $v\in V(D)-K$ has an ingoing arc $u\mathbin{\longrightarrow}v$ for some $u\in… Expand

Algorithmic aspects of quasi-kernels

- Computer Science, Mathematics
- ArXiv
- 2021

It is shown that, not only sink-free digraphs occasionally fail to contain two disjoint quasi-kernels, but it is computationally hard to distinguish those that do from those that don't, and it is proved that the problem of computing a small quasikernel is polynomial time solvable for orientations of trees but is computationationally hard in most other cases. Expand

J ul 2 02 1 ALGORITHMIC ASPECTS OF QUASI-KERNELS

- 2021

In a digraph, a quasi-kernel is a subset of vertices that is independent and such that every vertex can reach some vertex in that set via a directed path of length at most two. Whereas Chvátal and… Expand

Problems that I would like Somebody to Solve

- 2020

3 Some Smaller Problems 5 3.1 Slow Tribonacci Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 An Adversarial Chernoff Bound . . . . . . . . . . . . . . . . . . . . . . . .… Expand

#### References

SHOWING 1-10 OF 10 REFERENCES

Disjoint quasi-kernels in digraphs

- Mathematics
- 2008

A quasi-kernel in a digraph is an independent set of vertices such that any vertex in the digraph can reach some vertex in the set via a directed path of length at most two. Chvatal and Lovasz proved… Expand

On the number of quasi-kernels in digraphs

- Computer Science
- J. Graph Theory
- 2004

In 1974, Chvátal and Lovász proved that every digraph has a vertex set D 1⁄4 (V, A), and it is shown that for every v 2 V X there exists x 2 X such that vx 2 A. Expand

Every Planar Map Is Four Colorable

- Mathematics
- 1989

As has become standard, the four color map problem will be considered in the dual sense as the problem of whether the vertices of every planar graph (without loops) can be colored with at most four… Expand

On weakly ordered systems

- Mathematics
- 1946

The statement "x>y" may be read "x dominates y." Transitivity is not assumed ; a transitive weakly ordered system is a partially ordered system. By a solution of a weakly ordered system is meant a… Expand

About quasi-kernels in a digraph

- Computer Science, Mathematics
- Discret. Math.
- 1996

It is proved that every graph without kernel has at least three distinct quasi-kernels. Expand

Planar kernel and grundy with d≤3, dout≤2, din≤2 are NP-complete

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1981

Abstract It is proved that the questions whether a finite diagraph G has a kernel K or a Sprague—Grundy function g are NP-complete even if G is a cyclic planar digraph with degree constraints d out (… Expand

On the computational complexity of finding a kernel

- Report No. CRM- 300, Centre de Recherches Mathématiques, Université de Montréal,
- 1973