کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650615 1632449 2006 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Perfect graphs, kernels, and cores of cooperative games
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Perfect graphs, kernels, and cores of cooperative games
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2336–2354
نویسندگان
, ,