Perfect graphs, kernels, and cores of cooperative games

E. Boros, V. Gurvich

Research output: Contribution to journalArticlepeer-review

54 Scopus citations


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
Issue number19-20
StatePublished - Oct 6 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


  • 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


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

Cite this