# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# 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

### 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

### 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