Kernels in digraphs that are not kernel perfect

DOI10.1016/j.disc.2012.05.004zbMath1246.05066OpenAlexW2044021461MaRDI QIDQ442354

Sjur Dyrkolbotn, Michał Walicki

Publication date: 10 August 2012

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

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

zbMATH Keywords

parity conditionbreaking odd cyclesdigraph kernelnot kernel perfectundirected path parity

Mathematics Subject Classification ID

Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items

Kernels of digraphs with finitely many ends

Cites Work

• Expressive power of digraph solvability
• Graph theoretical structures in logic programs and default theories
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• On kernels and semikernels of digraphs
• A graph-theoretic approach to default logic
• On kernels, defaults and even graphs
• Combinatorial game theory foundations applied to digraph kernels
• On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and \(n\)-person games
• Perfect graphs, kernels, and cores of cooperative games
• Solutions of irreflexive relations
• On a Theorem of Richardson