Tag - Graphs
Short Rainbow Cycles in Sparse Graphs
Wed, Mar 7, 2018 11:00 CET
Speakers: Tony Huynh
Let \(G\) be a simple \(n\)-vertex graph and \(c\) be a colouring of \(E(G)\) with \(n\) colours, where each colour class has size at least \(2\). We prove that \(G\) contains a rainbow cycle of length at most \(\lceil \frac{n}{2} \rceil\), which is best possible. Our result settles a special case of a strengthening of the Caccetta-Häggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.
Intersection Graphs of Rays and Grounded Segments
Tue, Jun 6, 2017 12:30 CEST
Speakers: Till Miltzow
Excluded minors for isometric embeddings of graphs in $\ell_\infty^k$-spaces
Wed, May 31, 2017 12:30 CEST
Speakers: Carole Muller
Generalizations of the geometric de Bruijn-Erdos Theorem
Wed, Feb 15, 2017 12:30 CET
Speakers: Pierre Aboulker
Searching edges in the overlap of two plane graphs
Wed, Jan 18, 2017 12:00 CET