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:
AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s}, |
TITLE | = | {A conjecture on hypergraph orientation}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2008}, |
NUMBER | = | {QP-2008-02} |