Kernels in perfect line-graphs
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.
scientific article; zbMATH DE number 4135994