Title: An Excluded Minor Characterization of Seymour Graphs
Authors: Alexander Ageev, Andras Sebo, Zoltan Szigeti
Sobolev Institute of Mathematics, Novosibirsk, Russia,
and Laboratoire G-SCOP, Grenoble France
Abstract:
A graph $G$ is said to be a {\em Seymour graph} if for any edge set
$F$ there exist $|F|$ pairwise disjoint cuts each containing exactly
one element of $F$, provided for every circuit $C$ of $G$ the
necessary condition $|C\cap F|\le |C\setminus F|$ is
satisfied. Seymour graphs behave well with respect to some integer
programs including multiflow problems, or more generally odd cut
packings, and are closely related to matching theory.
A first coNP characterization of Seymour graphs has been shown by
Ageev, Kostochka and Szigeti, the recognition problem has been solved
in a particular case by Gerards, and the related cut packing problem
has been solved in the corresponding special cases. In this article
{\em we show a new, minor-producing operation that keeps this
property, and prove excluded minor characterizations of Seymour
graphs: the operation is the contraction of full stars, or of odd
circuits.} This sharpens the previous results, providing at the same
time a simpler and self-contained algorithmic proof of the existing
characterizations as well, still using methods of matching theory and
its generalizations.
Dualizing the planar special case, Seymour graphs are becoming those
for which the cut condition is sufficient for the existence of
disjoint paths for any set of demand pairs. Either the disjoint paths
or a forbidden minor can be found in polynomial time.