**Monday, 14:15 - 14:40 h, Room: H 3005**

**Serguei Norine**

Pairs of disjoint cycles

**Coauthors: Robin Thomas, Hein van der Holst**

**Abstract:**

We will describe a polynomial-time algorithm which determines whether an input graph contains a pair of disjoint cycles with the given property. In particular, it allows one to test whether a graph has two disjoint odd cycles, whether it has two disjoint cycles, one non-zero modulo 3 and the other non-zero modulo 5, whether a graph embedded in a surface has two disjoint homologically non-trivial cycles, and whether a given embedding of a graph in *3*-space is linkless.

The algorithm is based on an efficient characterization of the span of a certain collection of matrices indexed by pairs of disjoint cycles, extending a theorem of van der Holst and a characterization of linklessly embeddable graphs due to Robertson, Seymour and Thomas.

Talk 3 of the invited session Mon.2.H 3005

**"Structural graph theory and methods"** [...]

Cluster 2

**"Combinatorial optimization"** [...]