Perfect graphs, kernels, and cores of cooperative games

DOI10.1016/j.disc.2005.12.031zbMath1103.05034OpenAlexW1969590881MaRDI QIDQ2433701

Endre Boros, Vladimir A. Gurvich

Publication date: 30 October 2006

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

Full work available at URL: https://doi.org/10.1016/j.disc.2005.12.031

zbMATH Keywords

game formkernel-perfect graphstable family of coalitionskernel-solvable graphsnormal hypergraphsstable effectivity functions

Mathematics Subject Classification ID

Cooperative games (91A12) Games involving graphs (91A43) Perfect graphs (05C17)

Related Items (47)

Kernels by monochromatic paths and color-perfect digraphs ⋮ Richardson's theorem in \(H\)-coloured digraphs ⋮ Some results on the structure of kernel-perfect and critical kernel-imperfect digraphs ⋮ H-absorbence and H-independence in 3-quasi-transitive H-coloured digraphs. ⋮ A characterization of locally semicomplete CKI-digraphs ⋮ \(H\)-kernels in infinite digraphs ⋮ A corrected version of the Duchet kernel conjecture ⋮ H-kernels by walks in an \(R_H (D)\) digraph ⋮ Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3 ⋮ Kernels by rainbow paths in arc-colored tournaments ⋮ Algorithmic aspects of small quasi-kernels ⋮ Expressive power of digraph solvability ⋮ On the kernel and related problems in interval digraphs ⋮ \(\Pi\)-kernels in digraphs ⋮ Alternating kernels ⋮ Finding kernels or solving SAT ⋮ From kernels in directed graphs to fixed points and negative cycles in Boolean networks ⋮ Disjoint quasi-kernels in digraphs ⋮ \(k\)-colored kernels ⋮ Kernels in digraphs that are not kernel perfect ⋮ \(k\)-kernels in \(k\)-transitive and \(k\)-quasi-transitive digraphs ⋮ A new characterization of perfect graphs ⋮ \((k + 1)\)-kernels and the number of \(k\)-kings in \(k\)-quasi-transitive digraphs ⋮ War and peace in veto voting ⋮ Robust correspondence recognition for computer vision ⋮ Propositional discourse logic ⋮ On panchromatic digraphs and the panchromatic number ⋮ On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs ⋮ Kernels by properly colored paths in arc-colored digraphs ⋮ A Richardson's theorem version for \(\Pi\)-kernels ⋮ A note on kernels and Sperner's Lemma ⋮ Kernels by monochromatic paths in digraphs with covering number 2 ⋮ A polyhedral approach to the stability of a family of coalitions ⋮ On effectivity functions of game forms ⋮ Perfect graphs with polynomially computable kernels ⋮ CKI-digraphs, generalized sums and partitions of digraphs ⋮ $H$-kernels by walks in subdivision digraph ⋮ \(H\)-kernels and \(H\)-obstructions in \(H\)-colored digraphs ⋮ Domination in Digraphs ⋮ About \((k, l)\)-kernels, semikernels and Grundy functions in partial line digraphs ⋮ On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs ⋮ Quasi-Transitive Digraphs and Their Extensions ⋮ Miscellaneous Digraph Classes ⋮ Perfect Digraphs ⋮ \((k-1)\)-kernels in strong \(k\)-transitive digraphs ⋮ An extension of Richardson's theorem in m-colored digraphs ⋮ Richardson's theorem for \(k\)-colored kernels in strongly connected digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On a class of kernel-perfect and kernel-perfect-critical graphs
• On kernels and semikernels of digraphs
• Orientations of graphs in kernel theory
• Kernels in perfect line-graphs
• Necessary and sufficient conditions for stability of effectivity functions
• On kernel-perfect critical digraphs
• A parity digraph has a kernel
• A theorem about a conjecture of H. Meyniel on kernel-perfect graphs
• A new method to extend kernel-perfect graphs to kernel-perfect critical graphs
• Parity graphs are kernel-M-solvable
• Perfect graphs are kernel solvable
• A note on kernel-critical graphs
• Cores of effectivity functions and implementation theory
• A counterexample to a conjecture of Meyniel on kernel-perfect graphs
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• Cores of partitioning games
• Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes
• Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs)
• Extending kernel perfect digraphs to kernel perfect critical digraphs
• Strongly balanced cooperative games
• Perfectly orderable graphs and almost all perfect graphs are kernel \(M\)- solvable
• Colorings and orientations of graphs
• An algorithm for fraternal orientation of graphs
• A combinatorial problem in logic
• Combinatorial designs related to the strong perfect graph conjecture
• Stable families of coalitions and normal hypergraphs
• Some operations preserving the existence of kernels
• Normal fraternally orientable graphs satisfy the strong perfect graph conjecture
• In-tournament digraphs
• New extensions of kernel perfect digraphs to kernel imperfect critical digraphs
• A characterization of normal fraternally orientable perfect graphs
• Fractional kernels in digraphs
• A corrected version of the Duchet kernel conjecture
• A circular graph---counterexample to the Duchet kernel conjecture
• On certain polytopes associated with graphs
• Progress on perfect graphs
• On a lemma of Scarf.
• On kernel-perfect orientations of line graphs
• Kernels in directed graphs: A poison game
• On kernels in i-triangulated graphs
• Kernels in some orientations of comparability graphs
• The list chromatic index of a bipartite multigraph
• About quasi-kernels in a digraph
• Stable effectivity functions and perfect graphs
• Recognizing Berge graphs
• Anti-blocking polyhedra
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• Recent problems and results about kernels in directed graphs
• Solutions of irreflexive relations
• Kernels in the closure of coloured digraphs
• On graphs all of whose {C_3, T_3}-free arc colorations are kernel-perfect
• KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition
• Von Neumann-Morgenstern solutions to cooperative games without side payments
• A sufficient condition for a digraph to be kernel-perfect
• Graphes Noyau-Parfaits
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Complex analysis and convolution operators
• Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions
• On the orientation of meyniel graphs
• Perfect zero–one matrices
• An inductive method for constructing mimmal balanced collections of finite sets
• The Core of an N Person Game
• College Admissions and the Stability of Marriage

This page was built for publication: Perfect graphs, kernels, and cores of cooperative games