×

Kernels in perfect line-graphs. (English) Zbl 0694.05054

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.
Reviewer: F.Maffray

MSC:

05C99 Graph theory
Full Text: DOI