KERNELS IN PERFECT LINE-GRAPHS

被引：43

作者：

MAFFRAY, F

机构：

[1] Department of Computer Science, University of Toronto, Toronto

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1992年 / 55卷 / 01期

关键词：

D O I：

10.1016/0095-8956(92)90028-V

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. © 1992.

引用

页码：1 / 8

页数：8