TR-2003-11

A note on parity constrained orientations

Tamás Király, Jácint Szabó

Published in:
Combinatorica Volume 29, Number 5 (2009), 619-628.

This note extends the results of Frank, Jordán, and Szigeti on parity constrained orientations with connectivity requirements. Given a hypergraph H, a non-negative intersecting supermodular set function p, and a preferred in-degree parity for every node, a formula is given on the minimum number of nodes with wrong in-degree parity in an orientation of H covering p. It is shown that the minimum number of nodes with wrong in-degree parity in a strongly connected orientation cannot be characterized by a similar formula.

Bibtex entry:

@techreport{egres-03-11,

AUTHOR	=	{Kir{\'a}ly, Tam{\'a}s and Szab{\'o}, J{\'a}cint},
TITLE	=	{A note on parity constrained orientations},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2003},
NUMBER	=	{TR-2003-11}

}