**UBC Mathematics Department**

*http://www.math.ubc.ca*

## Colloquium Abstract: Professor Richard Anstee, Mathematics,
UBC

*Matching Theory: Two half edges are better than a whole edge*

For graphs, we refer to the degree of a vertex as the number of edges
in the graph incident with the vertex. Given a graph G=(V,E) we are often
interested in finding a subgraph H=(V,E') of G (E' is a subset of E) which
satisfies constraints on its degrees. For example a perfect matching in a
graph corresponds to a subgraph all of whose degrees are 1.

A somewhat strange version of this is to consider 'subgraphs' where we
are allowed to take an edge e a fractional amount x(e) with x(e) in the
interval [0,1]. Such a choice for e contributes x(e) to the degrees at each
endpoint of e. The problem of degree constrained subgraphs becomes much
easier in this setting (becomes a network flow problem) but the answer is
hardly interesting to graph theorists. So we must investigate ways that
we can preserve the degree constraints while making x(e) either 0 or 1.
These investigations have yielded fast algorithms, new existence theorems, a
quick edge colouring heuristic, and graph decompositions.

Return to this week's seminars