A note on kernels in h-perfect graphs

Tamás Király, Júlia Pap


Boros and Gurvich showed that every clique-acyclic superorientation of a perfect graph has a kernel. We prove the following extension of their result: if G is an h-perfect graph, then every clique-acyclic and odd-hole-acyclic superorientation of G has a kernel. We propose a conjecture related to Scarf's Lemma that would imply the reverse direction of the Boros-Gurvich theorem without relying on the Strong Perfect Graph Theorem.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {A note on kernels in h-perfect graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2007},
NUMBER = {TR-2007-03}

Last modification: 29.12.2020. Please email your comments to Tamás Király!