Perfect graphs, kernels, and cores of cooperative games

E. Boros, V. Gurvich

Research output: Contribution to journalArticlepeer-review

53 Scopus citations

Abstract

A kernel of a directed graph D is defined as an independent set which is reachable from each outside vertex by an arc. A graph G is called kernel-solvable if an orientation D of G has a kernel whenever each clique of G has a kernel in D. The notion of kernel-solvability has important applications in combinatorics, list coloring, and game theory. It turns out that kernel-solvability is equivalent to perfectness, as it was conjectured by Berge and Duchet in 1983. These and other kernel-related results are the subject of the present survey. Many of these results are independent of the strong perfect graph conjecture, yet, the recent proof of this conjecture and the efficient recognition of perfect graphs have several important implications, in particular in game theory, which are also included here.

Original languageEnglish (US)
Pages (from-to)2336-2354
Number of pages19
JournalDiscrete Mathematics
Volume306
Issue number19-20
DOIs
StatePublished - Oct 6 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Coalition
  • Cooperative game
  • Effectivity function
  • Game form
  • Kernel
  • Kernel-perfect graph
  • Kernel-solvable graphs
  • Normal hypergraphs
  • Perfect graphs
  • Stable effectivity functions
  • Stable family of coalitions

Fingerprint

Dive into the research topics of 'Perfect graphs, kernels, and cores of cooperative games'. Together they form a unique fingerprint.

Cite this