A note on kernels and Sperner's Lemma

DOI10.1016/j.dam.2009.07.005zbMath1227.05153OpenAlexW2084754653WikidataQ124966120 ScholiaQ124966120MaRDI QIDQ967389

Tamás Király, Júlia Pap

Publication date: 28 April 2010

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

Full work available at URL: https://doi.org/10.1016/j.dam.2009.07.005

zbMATH Keywords

perfect graphSperner's Lemmaclique acyclic superorientationkernel solvable graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Perfect graphs (05C17)

Related Items (6)

A Polyhedral Description of Kernels ⋮ \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma ⋮ Stable multicommodity flows ⋮ New and simple algorithms for stable flow problems ⋮ Perfect graphs with polynomially computable kernels ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

Cites Work

• A class of h-perfect graphs
• The strong perfect graph theorem
• Matrices with the Edmonds-Johnson property
• Perfect graphs are kernel solvable
• Fractional kernels in digraphs
• Polyhedral characterizations and perfection of line graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Applying Lehman's theorems to packing problems
• Perfect graphs, kernels, and cores of cooperative games
• Anti-blocking polyhedra
• Normal hypergraphs and the perfect graph conjecture
• Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor
• Lectures on Polytopes
• The Core of an N Person Game

This page was built for publication: A note on kernels and Sperner's Lemma