DIMACS TR: 2003-10
Perfect Graphs, Kernels, and Cores of Cooperative Games
Authors: E. Boros and V. Gurvich
ABSTRACT
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