Solving the kernel perfect problem by (simple) forbidden subdigraphs for digraphs in some families of generalized tournaments and generalized bipartite tournaments
2018
A digraph such that every proper induced subdigraph has a kernel is said to
be \emph{kernel perfect} (KP for short) (\emph{critical kernel imperfect} (CKI
for short) resp.) if the digraph has a kernel (does not have a kernel resp.).
The unique CKI-tournament is $\overrightarrow{C}_3$ and the unique
KP-tournaments are the transitive tournaments, however bipartite tournaments
are KP. In this paper we characterize the CKI- and KP-digraphs for the
following families of digraphs: locally in-/out-semicomplete, asymmetric
arc-locally in-/out-semicomplete, asymmetric $3$-quasi-transitive and
asymmetric $3$-anti-quasi-transitive $TT_3$-free and we state that the problem
of determining whether a digraph of one of these families is CKI is polynomial,
giving a solution to a problem closely related to the following conjecture
posted by Bang-Jensen in 1998: the kernel problem is polynomially solvable for
locally in-semicomplete digraphs.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
19
References
1
Citations
NaN
KQI