Kernels in perfect line-graphs (Q908943)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Kernels in perfect line-graphs
scientific article

    Statements

    Kernels in perfect line-graphs (English)
    0 references
    0 references
    1992
    0 references
    A kernel of a directed graph D is a set of vertices which is both independent and absorbant. In 1983, Berge and Duchet conjectured that an undirected graph G is perfect if and only if the following condition is satisfied: ``If D is any orientation of G such that every clique of D has a kernel, then D has a kernel.'' We prove here that the conjecture holds when G is the line-graph of another graph H, i.e., G represents the incidence between the edges of H.
    0 references
    graph theory
    0 references
    game theory
    0 references
    perfect graphs
    0 references
    coloration
    0 references
    kernel
    0 references
    directed graph
    0 references
    line-graph
    0 references

    Identifiers