Perfect graphs, kernels, and cores of cooperative games

DOI10.1016/J.DISC.2005.12.031zbMATH Open1103.05034OpenAlexW1969590881MaRDI QIDQ2433701FDOQ2433701

Authors: Endre Boros, Vladimir 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

Recommendations

• Perfect graphs are kernel solvable
• scientific article; zbMATH DE number 4095497
• On kernels in perfect graphs
• Kernels in perfect line-graphs
• A note on kernels and Sperner's Lemma

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)

Cites Work

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

Cited In (49)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2433701)