ICS Theory Group

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.