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

    Identifiers