Kernels in some orientations of comparability graphs (Q1823257)

From MaRDI portal
Revision as of 10:49, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Kernels in some orientations of comparability graphs
scientific article

    Statements

    Kernels in some orientations of comparability graphs (English)
    0 references
    1989
    0 references
    The following conjecture of H. Meyniel is dealt with: Let G be a perfect graph and let D be an orientation of G such that all 3-circuits of D have at least two reversible arcs. Then D has a kernel. The author has proved the conjecture for comparability graphs. The method of the proof is closely related to the method of \textit{B. Sands, N. Sauer} and \textit{R. Woodrow} [J. Comb. Theory, Ser. B 33, 271-275 (1982; Zbl 0488.05036)].
    0 references
    0 references
    directed graphs
    0 references
    perfect graph
    0 references
    kernel
    0 references