Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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