Kernels in perfect line-graphs
type: Item
instance of: scholarly article
title: Kernels in perfect line-graphs
zbMATH Open document ID: 0694.05054
DOI: 10.1016/0095-8956(92)90028-V
author: Frédéric Maffray
published in: Journal of Combinatorial Theory. Series B
publication date: 1992-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4135994
zbMATH Keywords: graph theory
zbMATH Keywords: game theory
zbMATH Keywords: perfect graphs
zbMATH Keywords: coloration
zbMATH Keywords: kernel
zbMATH Keywords: directed graph
zbMATH Keywords: line-graph
Wikidata QID: Q56388847
MaRDI profile type: Publication
full work available at URL: 0095-8956(92)90028-v
OpenAlex ID: W1998964930
description: scientific article; zbMATH DE number 4135994