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.