Title: A generalized Tutte-Berge formula for f-bounded subgraphs
Speaker: Zishen Qu
Abstract: The Tutte-Berge formula gives the size of a maximum matching in a graph
G. A generalized version of this formula can be given to find maximum
size spanning subgraphs where the degree at each vertex is bounded by f,
similar to the generalization of perfect matching to f-factor. Given
$(G, f)$, where $f$ is a positive integer function on the vertices, one
seeks to obtain a subgraph $H$ such that $d_H(v) \leq f(v)$ for all $v
\in V(G)$. Subject to this we seek to maximize $|E(H)|$. A generalized
Tutte-Berge formula produces the size of this $E(H)$, and was proven by
Schrijver. In this talk, we give an introduction and a short history for
this formula, and provide an alternative proof.
Joint work with Douglas B. West.
