| 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