TR-2007-03

A note on kernels in h-perfect graphs

Tamás Király, Júlia Pap



Abstract

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:

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


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