Reducible Configurations for the Cycle–Double–Cover–Conjecture

Andreas Huck Hannover, Germany

The well–known Cycle–Double–Cover–Conjecture (CDC–Conjecture) of Seymour and Szekeres states that each bridgeless multigraph G has a CDC, i.e. a collection of cycles covering each edge of G exactly twice. Here cycles are Eulerian subgraphs of G which need not be connected. A strengthening of the CDC–Conjecture is the 5–CDC–Conjecture stating that each bridgeless multigraph has a 5–CDC, i.e. a CDC consisting of only five cycles.

I present a strategy for attacking the (5–)CDC–Conjecture which is borrowed from the proof of the Four–Colour–Theorem. A configuration (i.e. a multigraph together with some pending edges incident with only one vertex) is called irreducible if it cannot be contained in a minimal counterexample of the (5–)CDC–Conjecture. For instance, Goddyn verified that all circuits of length at most 9 together with a pending edges at each vertex are irreducible for the CDC–conjecture so that each minimal counterexample of this conjecture has girth at least 10. Motivated by this result, I looked for algorithms (reduction methods) for verifying irreducibility of given configurations so that boring case–checkings can be left to a computer. Among other things, these algorithms lead to the following results:

(1) Each minimal counterexample of the CDC–Conjecture has girth at least 12.

(2) Each minimal counterexample of the 5–CDC–Conjecture has girth at least 10.

(3) Each minimal counterexample of the restricted 5–CDC–Conjecture (each bridgeless multigraph without Petersen–minor has a 5–CDC) has girth at least 8.

Remark: I obtained these results before my university position expired three years ago. Since that time, I have an employment in the private industry which does not leave me much time for researching and teaching. Therefore I would be very grateful for informations about positions where I could act as before.