Perfect graphs are kernel solvable

DOI10.1016/0012-365X(95)00096-FzbMath0861.05053WikidataQ59560913 ScholiaQ59560913MaRDI QIDQ1126176

Endre Boros, Vladimir A. Gurvich

Publication date: 4 May 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

directed graphkernelperfect graphkernel solvable graphscore solvabilitysuperorientation

Mathematics Subject Classification ID

Games involving graphs (91A43) Structural characterization of families of graphs (05C75)

Related Items

A Polyhedral Description of Kernels ⋮ Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3 ⋮ On the kernel and related problems in interval digraphs ⋮ Perfect graphs, kernels, and cores of cooperative games ⋮ Kernels and perfectness in arc-local tournament digraphs ⋮ A new characterization of perfect graphs ⋮ Kernels in weighted digraphs ⋮ Stable effectivity functions and perfect graphs ⋮ On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs ⋮ Fractional solutions for capacitated NTU-games, with applications to stable matchings ⋮ A note on kernels and Sperner's Lemma ⋮ A polyhedral approach to the stability of a family of coalitions ⋮ Stable matchings in three-sided systems with cyclic preferences ⋮ Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree ⋮ On effectivity functions of game forms ⋮ Kernels in quasi-transitive digraphs ⋮ On kernel-less clique-acyclic orientations of minimally imperfect graphs ⋮ Perfect graphs with polynomially computable kernels ⋮ Some sufficient conditions for the existence of kernels in infinite digraphs ⋮ Stable families of coalitions and normal hypergraphs ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Vertex- and edge-minimal and locally minimal graphs ⋮ Miscellaneous Digraph Classes ⋮ Perfect Digraphs ⋮ Some operations preserving the existence of kernels ⋮ Game-perfect semiorientations of forests

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On kernels in perfect graphs
• Necessary and sufficient conditions for stability of effectivity functions
• Cores of effectivity functions and implementation theory
• Strongly balanced cooperative games
• Stable families of coalitions and normal hypergraphs
• Fractional kernels in digraphs
• On certain polytopes associated with graphs
• On kernels in i-triangulated graphs
• Stable effectivity functions and perfect graphs
• A characterization of perfect graphs
• Perfect zero–one matrices
• The Core of an N Person Game
• Blocking and anti-blocking pairs of polyhedra