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.

 

  online loans . Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.