×

Solving the kernel perfect problem by (simple) forbidden subdigraphs for digraphs in some families of generalized tournaments and generalized bipartite tournaments. (English) Zbl 1403.05055

Summary: A digraph such that every proper induced subdigraph has a kernel is said to be kernel perfect (KP for short) (critical kernel imperfect (CKI for short) resp.) if the digraph has a kernel (does not have a kernel resp.). The unique CKI-tournament is \(\vec 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-antiquasi-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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C75 Structural characterization of families of graphs
05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: arXiv Link