from 1:30-3:35 in K9509, SFU
Friday November 29, 2000
Abstract:
An $r$-graph is any graph that can be obtained as a conic
combination of its own $1$-factors. Equivalenty, an $r$-graph
is an $r$-regular graph such that at least $r$-edges leave each
odd-cardinality subset of nodes. An $r$-graph $(V,E)$ is
indecomposable if its edge set $E$ cannot be partitioned
as $E=E_1 \cup E_2$ so that $(V,E_1)$ and $(V,E_2)$ are both
$r$-graphs. We construct an indecomposable $r$-graph for every
integer $r\geq 4$. This answers a question posed by Seymour
and implies that the coefficients in the Schrijver System
(minimal TDI system) of the $T$-cut polyhedron are not bounded
by any constant.
A graph in which every two $1$-factors intersect is said to be poorly matchable. Every poorly matchable $r$-graph is indecomposable. We show that the converse of this statement is false for $r\geq 4$. Further, we construct a poorly matchable $r$-graph for every $r\geq 4$.
Related topics Fulkerson Coloring Conjecture, Seymour's Coloring Conjecture, Hilbert bases, packing $T$-joins, colorings and flows.