Fractional kernels in digraphs

DOI10.1006/JCTB.1997.1731MaRDI QIDQ1366601zbMATH OpenOpenAlexFDO

Authors Ron Aharoni, Ron Holzman

Publication date 15 September 1997

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/be3f4379c55b3ccf024efb07b50a1c1f04d28180

zbMATH Keywords

digraphfractional kernelperfect graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Review text

We define a fractional version of the notion of ``kernels in digraphs, and prove that every clique-acyclic digraph (i.e., one in which no clique contains a cycle) has a fractional kernel. Using this we give a short proof of the recent result of Boros and Gurvich (proving a conjecture of Berge and Duchet) that every clique-acyclic orientation of a perfect graph has a kernel.

Recommendations

• On kernels in perfect graphs
• On kernel-less clique-acyclic orientations of minimally imperfect graphs
• Perfect graphs with polynomially computable kernels
• Kernels in perfect line-graphs
• Perfect digraphs

Cites work

• A characterization of perfect graphs
• College Admissions and the Stability of Marriage
• Kernels in perfect line-graphs
• On kernels in i-triangulated graphs
• The Core of an N Person Game

Cited in

(17)

• Perfect graphs are kernel solvable
• Stable families of coalitions and normal hypergraphs
• On a lemma of Scarf.
• Perfect graphs with polynomially computable kernels
• Absorbant of generalized de Bruijn digraphs
• Perfect graphs, kernels, and cores of cooperative games
• Kernels in weighted digraphs
• A Polyhedral Description of Kernels
• scientific article; zbMATH DE number 5769858 (Why is no real title available?)
• Gallai colorings and domination in multipartite digraphs
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
• On kernel-less clique-acyclic orientations of minimally imperfect graphs
• Local stability in kidney exchange programs
• Scarf's algorithm on arborescence hypergraphs
• A note on kernels and Sperner's Lemma
• A polyhedral approach to the stability of a family of coalitions

This page was built for publication: Fractional kernels in digraphs

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