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