论文标题
走向小的准内核猜想
Towards the Small Quasi-Kernel Conjecture
论文作者
论文摘要
令$ d =（v，a）$为挖掘物。如果$ k $是$ d $中的独立套件，则顶点$ k \ subseteq v $是$ d $的准内核，对于每个v \ setminus k $ in v \ setminus k $，$ v $的每个顶点$ v \，最多是$ k $的2。 1974年，Chvátal和Lovász证明了每个Digraph都有准内核。 P. L.Erdős和L. A.Székely在1976年猜想，如果每个顶点$ d $都有正化，则$ d $的大小为$ | v |/2 $。该猜想仅用于狭窄类别的狭窄类别，例如半完整的多部分，准传播或局部分离的挖掘。在本说明中，我们陈述了所有digraphs的类似猜想，表明这两个猜想是等效的，并证明了两个猜想对包含所有4色图的所有方向（尤其是所有平面图）的一类挖掘物。
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átal and Lovász proved that every digraph has a quasi-kernel. P. L. Erdős and L. A. Székely 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, such as semicomplete multipartite, quasi-transitive, or locally demicomplete digraphs. In this note, we state a similar conjecture for all digraphs, show that the two conjectures are equivalent, and prove that both conjectures hold for a class of digraphs containing all orientations of 4-colorable graphs (in particular, of all planar graphs).
