KERNELS IN PERFECT LINE-GRAPHS

被引:43
作者
MAFFRAY, F
机构
[1] Department of Computer Science, University of Toronto, Toronto
关键词
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
相关论文
共 20 条
  • [1] BERGE C, 1983, S MSH
  • [2] Berge C., 1984, TOPICS PERFECT GRAPH
  • [3] Berge C, 1985, GRAPHS
  • [4] BERGE C, UNPUB KENELS PERFECT
  • [5] BERGE C, 1987, 1986 P BURNS RASP M
  • [6] BERGE C, 1984, TOPICS PERFECT GRAPH, P57
  • [7] A PARITY DIGRAPH HAS A KERNEL
    BLIDIA, M
    [J]. COMBINATORICA, 1986, 6 (01) : 23 - 27
  • [8] BLIDIA M, 1990, RUTCOR390 RES REP
  • [9] BLIDIA M, 1984, THESIS U PARIS L
  • [10] BLIDIA M, UNPUB KERNELS PARITY