#
Monday Lecture and Colloquium

**Monday, December 16, 2013 **

Technische Universität Berlin

Institut für Mathematik

Straße des 17. Juni 136

10623 Berlin

room MA 041

** Lecture - 14:15**

### Sang-Il Oum - KAIST, South Korea

### Vertex-minors and split decompositions of graphs

*Abstract:*

The vertex-minor relation of graphs is defined in terms of local complementation and vertex deletion. This concept naturally arises in the study of circle graphs (intersection graphs of chords in a circle) and rank-width of graphs. Interestingly many theorems on graph minors have analogous results in terms of vertex-minors and there are some graph algorithms based on vertex-minors.
A split decomposition is a decomposition of graphs into tree-like structures recursively by splits, where a split is a partition of the vertex set so that the set of edges between parts forms a complete bipartite subgraphs.
A graph is prime if it does not admit non-trivial split decompositions.
We will discuss known results relating vertex-minors and split decompositions
and discuss a recent result on unavoidable vertex-minors in very large prime graphs.

** Colloquium - 16:00**

### Tuan Tran -
FU Berlin

### Turán density theorem for multipartite graphs

*Abstract:*

For a fixed graph H and an integer l > v(H), let d_l(H) be the minimum real number such that every l-partite graph whose edge densities between partition sets greater than d_l(H) contains a copy of H. Among other things, Bondy et al. (2006) showed that d_l(H) decreases to (_{X}(H)-2)/(_{X}(H)-1) when l tends to infinity. Recently, Pfender proved that for every integer k > 2 there exists C_k > 0 such that d_l(K_k)=(k-2)/(k-1) for all l > C_k. Using Pfender's strategy we are able to characterize graphs H with the property that d_l(H) = (_{X}(H)-2)/(_{X}(H)-1) for sufficiently large l depending on H.

The talk is based on a joint work with Lothar Narins.

Letzte Aktualisierung:
10.12.2013