Perfect graphs are kernel solvable
type: Item
instance of: scholarly article
title: Perfect graphs are kernel solvable
zbMATH Open document ID: 0861.05053
DOI: 10.1016/0012-365X(95)00096-F
author: Endre Boros
author: Vladimir Gurvich
published in: Discrete Mathematics
publication date: 1997-05-04T00:00:00Z
review text: A superorientation (direction) of a graph \(G\) is a directed graph \(D\) whose underlying undirected graph is \(G\), where pairs of reversible arcs are allowed. A subset \(S\) of the vertices of a directed graph \(D\) is called a kernel if it is a stable set and every vertex outside \(S\) has a successor in \(S\). A superorientation of \(D\) is said to be admissible if every (directed) clique has a kernel. An undirected graph \(G\) is called kernel solvable if every admissible superorientation of \(G\) has a kernel. In this important paper the authors prove, using results of game theory, the following conjecture of C. Berge and P. Duchet from 1983: Every perfect graph is kernel solvable. In addition, they give a partial answer for a second conjecture which states that, conversely, kernel solvable graphs are perfect, in proving that if a graph \(G\) is not perfect, then there exists a blow-up (substituting some vertices by cliques) of \(G\), which is not kernel solvable.
reviewed by: Konrad Engel
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 955080
zbMATH Keywords: core solvability
zbMATH Keywords: superorientation
zbMATH Keywords: directed graph
zbMATH Keywords: kernel
zbMATH Keywords: perfect graph
zbMATH Keywords: kernel solvable graphs
Wikidata QID: Q59560913
MaRDI profile type: Publication
cites work: Fractional kernels in digraphs
cites work: Q3941433
cites work: Q4094892
cites work: Q3216697
cites work: Q3222875
cites work: On kernels in perfect graphs
cites work: Stable effectivity functions and perfect graphs
cites work: Stable families of coalitions and normal hypergraphs
cites work: On certain polytopes associated with graphs
cites work: Q3809537
cites work: Q3795441
cites work: Blocking and anti-blocking pairs of polyhedra
cites work: Q3917914
cites work: Q3914792
cites work: Necessary and sufficient conditions for stability of effectivity functions
cites work: Strongly balanced cooperative games
cites work: A characterization of perfect graphs
cites work: Q5184934
cites work: On kernels in i-triangulated graphs
cites work: Q4407446
cites work: Cores of effectivity functions and implementation theory
cites work: Perfect zero–one matrices
cites work: The Core of an N Person Game
cites work: Q3680647
description: scientific article; zbMATH DE number 955080