DIMACS TR: 2003-10

Perfect Graphs, Kernels, and Cores of Cooperative Games

Authors: E. Boros and V. Gurvich


A kernel in a directed graph is an independent set, which is reachable from each other vertex by an arc. A directed graph in which every induced subgraph has a kernel is called kernel-perfect. The existence of a kernel in directed graphs, and in particular, kernel-perfect orientations of undirected graphs is strongly related to perfect graphs, and has several applications in combinatorics and game theory. These and related results are the subject of this survey. Though some of these results are independent of the Strong Perfect Graph Conjecture, the recent solution of this conjecture and the efficient recognition of perfect graphs have several important implications, in particular in game theory.

Key words: kernel, kernel-solvable graphs, perfect graphs, normal hypergraphs, Strong Perfect Graph Conjecture, Berge-Duchet conjecture; cooperative games, coalition, stable family of coalitions, game form, effectivity function, stable effectivity functions, Scarf theorem.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-10.ps.gz

DIMACS Home Page