QP-2008-02

A conjecture on hypergraph orientation

Tamás Király



Abstract

We propose a conjecture on the orientation of hypergraphs which have the property that no hyperedge intersects minimally a regular family of sets. The truth of the conjecture would imply that non-perfect graphs are not kernel-solvable - the only known proof of which is based on the Strong Perfect Graph Theorem. We show that the conjecture is true if the hypergraph contains a connected graph.


Bibtex entry:

@techreport{egresqp-08-02,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s},
TITLE = {A conjecture on hypergraph orientation},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {QP-2008-02}
}


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