Seminar of Graph Theory - Christian Rubio-Montiel (13.10.2016)

Thursday 13.10.2016 at 9:50, Lecture room M/213

10. 10. 2016 09.22 hod.
By: Martin Škoviera

Christian Rubio-Montiel:
On crossing families

Abstract:
A geometric graph is a graph drawn in the plane such that its n vertices are points in general position, and its edges are straight-line segments.
Two edge-disjoint geometric subgraphs *cross* if there is an edge in the first subgraph and an edge in the second subgraph that have an interior point in common. A set of edge-disjoint geometric subgraphs is called *mutually crossing* if any two of their elements cross. We show that for any geometric complete graph there always exists a set of mutually crossing 2-paths (paths of length 2) of size at least \sqrt{n/2}, and a set of mutually crossing claw graphs (a star of tree leaves) of size at least n/6.

This is a joint work with Dolores Lara (Departamento de Computación, CINVESTAV, Mexico).