An official website of the United States government
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 semicomplete 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).
more »
« less
This content will become publicly available on January 9, 2027
Distant Digraph Domination
A $$k$$-kernel in a digraph $$G$$ is a stable set $$X$$ of vertices such that every vertex of $$G$$ can be joined from $$X$$ by a directed path of length at most $$k$$. We prove three results about $$k$$-kernels. First, it was conjectured by Erdős and Székely in 1976 that every digraph $$G$$ with no source has a 2-kernel $|K|$ with $$|K|\le |G|/2$$. We prove this conjecture when $$G$$ is a split digraph (that is, its vertex set can be partitioned into a tournament and a stable set), improving a result of Langlois et al., who proved that every split digraph $$G$$ with no source has a 2-kernel of size at most $2|G|/3$. Second, the Erdős-Székely conjecture implies that in every digraph $$G$$ there is a 2-kernel $$K$$ such that the union of $$K$$ and its out-neighbours has size at least $|G|/2$. We prove that this is true if $V(G)$ can be partitioned into a tournament and an acyclic set. Third, in a recent paper, Spiro asked whether, for all $$k\ge 3$$, every strongly-connected digraph $$G$$ has a $$k$$-kernel of size at most about $|G|/(k+1)$. This remains open, but we prove that there is one of size at most about $|G|/(k-1)$.
more »
« less
- Award ID(s):
- 2154169
- PAR ID:
- 10688380
- Publisher / Repository:
- Australian National University
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 33
- Issue:
- 1
- ISSN:
- 1077-8926
- Subject(s) / Keyword(s):
- Theorical Computer Science Geometry and Topology Discrete Mathematics and Combinatorics Computational Theory and Mathematics Applied Mathematics
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We confirm a conjecture of Fox, Pach, and Suk, that for every d>0, there exists c>0 such that every n-vertex graph of VC-dimension at most d has a clique or stable set of size at least nc . This implies that, in the language of model theory, every graph definable in NIP structures has a clique or anti-clique of polynomial size, settling a conjecture of Chernikov, Starchenko, and Thomas. Our result also implies that every two-colourable tournament satisfies the tournament version of the Erdős-Hajnal conjecture, which completes the verification of the conjecture for six-vertex tournaments. The result extends to uniform hypergraphs of bounded VC-dimension as well. The proof method uses the ultra-strong regularity lemma for graphs of bounded VC-dimension proved by Lovász and Szegedy and the method of iterative sparsification introduced by the authors in an earlier paper.more » « less
-
We prove the Erdős–Hajnal conjecture for the five-vertex path P5; that is, there exists c>0 such that every n-vertex graph with no induced P5 has a clique or stable set of size at least nc. This completes the verification of the Erdős–Hajnal conjecture for all five-vertex graphs. Our methods combine probabilistic and structural ideas with the iterative sparsification framework introduced in the third and fourth papers in the series.more » « less
-
null (Ed.)Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c ∈ N such that for every graph G ∈ C there is a collection P of partitions (X, Y ) of the vertex set of G with |P| ≤ |V (G)| c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = ∅, then there is (X, Y ) ∈ P with K ⊆ X and S ⊆ Y . In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. G¨o¨os in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S, K of graphs and show that for every S ∈ S and K ∈ K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property.more » « less
-
Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c∈N such that for every graph G∈C there is a collection P of partitions (X,Y) of the vertex set of G with |P|≤|V(G)|c and with the following property: if K is a clique of G, and S is a stable set of G, and K∩S=∅, then there is (X,Y)∈P with K⊆X and S⊆Y. In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by Göös in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S,K of graphs and show that for every S∈S and K∈K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property.more » « less
