Kernels in perfect line-graphs (Q908943)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Kernels in perfect line-graphs |
scientific article; zbMATH DE number 4135994
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Kernels in perfect line-graphs |
scientific article; zbMATH DE number 4135994 |
Statements
Kernels in perfect line-graphs (English)
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
