# ICS 269, Fall 2001: Theory Seminar

## 2 November 2001:

Partitioning Series Parallel Graphs into v-Excluding Edge Coverings

Zheng Sun

Minimum edge covering is a well studied problem in graph theory. A relevant
problem is to partition a graph into as many disjoint edge
coverings as possible. Generally it is hard to get a lower bound of
the second problem on any class of graphs. But if we loosen the constraint of
'edge covering' by allowing one vertex not covered, there come some
interesting results.
We call a set of edges covering all vertices except $v$ a $v$-excluding edge
covering and denote it by $C(v)$. Then we show that a serial parallel graph
can be partitioned into $\kappa^{\prime}$ disjoint $C(v)$'s, where
$\kappa^{\prime}$ is the edge connectivity and $v$ is arbitrary. Furthermore,
though we can't make a formal conjection, we hope that planar graphs also
have such partitions with cardinality $\kappa^{\prime}$. And this proposition
on planar graph is stronger than the 4-Color Theorem.
Our talk will focus on an algorithmic proof on serial parallel graphs.