## Invited Session Mon.2.H 3005

#### Monday, 13:15 - 14:45 h, Room: H 3005

**Cluster 2: Combinatorial optimization** [...]

### Structural graph theory and methods

**Chair: Paul Wollan**

**Monday, 13:15 - 13:40 h, Room: H 3005, Talk 1**

**Sang-Il Oum**

Vertex-minors and pivot-minors of graphs

**Abstract:**

We will survey vertex- and pivot-minor relations of graphs

which are defined in terms of local complementation and pivot

operations, respectively, on graphs.

Many theorems on graph minors

can be extended to graph vertex- or pivot-minors.

We will discuss various known aspects

and then talk about partial results towards some conjectures

generalizing some of the deepest theorems in structural graph theory

including the graph minor theorem of Robertson and Seymour.

**Monday, 13:45 - 14:10 h, Room: H 3005, Talk 2**

**Gwenael Joret**

Excluded forest minors and the Erdös-Pósa Property

**Coauthors: Samuel Fiorini, David R. Wood**

**Abstract:**

A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph *H* as a minor has the so-called Erd?s-Pósa property; namely, there exists a function *f* depending only on *H* such that, for every graph *G* and every integer *k ∈ ***N**, either *G* has *k* vertex-disjoint subgraphs each containing *H* as a minor, or there exists a subset *X* of vertices of *G* with *|X| ≤ f(k)* such that *G - X* has no *H*-minor. While the best function *f* currently known is super-exponential in *k*, a *O(k **log* k) bound is known in the special case where *H* is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour, and Thomas on the pathwidth of graphs with an excluded forest-minor.

In this talk I will sketch a proof that the function *f* can be taken to be linear when *H* is a forest. This is best possible in the sense that no linear bound exists if *H* has a cycle.

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

**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.