Kernels in digraphs with covering number at most 3 (Q1861206)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Kernels in digraphs with covering number at most 3 |
scientific article |
Statements
Kernels in digraphs with covering number at most 3 (English)
0 references
16 March 2003
0 references
A digraph \(D\) is said to be kernel-perfect if every proper induced subdigraph of \(D\) possesses a kernel. In 1998, the author (with her coauthor Xuliang Li) published two sufficient conditions for a digraph \(D\) to be kernel-perfect, concerning digraphs with the covering number at most three, containing only symmetrical directed triangles. In this paper the class of \(M\)-oriented digraphs is considered and a common generalization of both previous conditions is presented. The main result is the following one: Let every directed triangle of a digraph \(D\) have at least two symmetrical arcs. If each directed cycle of length five in \(D\) has two diagonals or three symmetrical arcs, then \(D\) is kernel-perfect.
0 references
kernel
0 references
kernel-perfect digraph
0 references
covering number
0 references