A theorem about a conjecture of H. Meyniel on kernel-perfect graphs (Q1081612)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A theorem about a conjecture of H. Meyniel on kernel-perfect graphs |
scientific article |
Statements
A theorem about a conjecture of H. Meyniel on kernel-perfect graphs (English)
0 references
1986
0 references
An R-digraph (also called kernel-perfect graph) is a digraph such that all of its induced subdigraphs possess a kernel (that is an independent dominating subset). Meyniel's conjecture (suggested in the title) is that D is an R-digraph if all odd directed cycles of D possess two pseudodiagonals (a pseudo-diagonal is an arc which is not part of the cycle but with end vertices on the cycle). This conjecture was disproved by the author [ibid. 41, 105-107 (1982; Zbl 0484.05035)]. In a previous article [ibid. 48, 67-76 (1984; Zbl 0529.05024)], the author and \textit{V. Neumann-Lara} proved that any digraph, in which every odd directed cycle has 2 pseudodiagonals with consecutive terminal end vertices, is an R-digraph. The aim of the present article is to show that the same result holds with 2 pseudodiagonals of the form \((q,q+2)\) if D does not contain a directed triangle.
0 references
R-digraph
0 references
kernel-perfect graph
0 references
cycles
0 references