McGill University - School of Computer Science

Algorithms Seminar Fall 2001

Everybody is welcome!

DATE: Wednesday, November 14th
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: Toward the cycle double cover conjecture
SPEAKER: Matt Devos, Princeton University, Princeton NJ USA

The cycle double cover conjecture asserts that every bridgeless graph has a list of circuits so that every edge is contained in exactly two. This lovely conjecture has been the focus of considerable study and there are a number of interesting conjectured extensions. In this talk we give a survey of these extensions and we discuss some recent progress on one of them.

The particular problem we study is that of decomposing an Eulerian graph G into circuits under certain local constraints. More precisely, we assume that every vertex of G is equipped with a pairing of the incident edges, and our goal is to decompose G into circuits so that no circuit uses both edges from any one of these pairs. We conjecture that every 6-edge-connected Eulerian graph has such a decomposition and we show that (if true) this would imply the cycle double cover conjecture. We prove that such a decomposition exists whenever the graph is 2^18-edge-connected.

This is joint work with Paul Seymour

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.