In our research seminar, members of the institute and external visitors give presentations on their research topics. If not otherwise specified, the seminar takes place on Tuesdays at 13:15 in our seminar room.

• 13.01.2025:  Recent Developments in Distributed Δ-Coloring,  Manuel Jakob

  • Abstract: Graph coloring is one of the central problems in distributed computing because it captures the fundamental challenge of symmetry breaking using only local information. In particular, the Δ+1 coloring problem has been extensively studied, as it can still be solved greedily in a centralized setting. While a Δ+1 coloring can be computed in log*(n) rounds in the LOCAL model on constant-degree graphs, the closely related Δ-coloring problem is significantly more challenging. The Δ-coloring problem admits an Ω(log n) round lower bound, established in [BFHKLRSU, STOC'16].

    For many years, the algorithm of [Ghaffari, Hirvonen, Kuhn, Maus, PODC'18] was the best known algorithm, leaving a gap to the known lower bound for constant-degree graphs. Recently, this gap has begun to close. First, [Bourreau, Brandt, Nolin, STOC'25] introduced the first algorithm improving upon this result, achieving a log(n)log*(n)-round algorithm. Shortly thereafter, [Jakob, Maus, PODC'25] introduced a log(n)-round algorithm for locally dense graphs with constant degree, and [Bourreau, Brandt, Nolin, SODA'25] obtained a log(n)-round algorithm for general constant-degree graphs.

    This talk presents these recent breakthroughs and the techniques that have led to significant improvements in algorithms for Δ-coloring.

• 20.01.2025: TBA - Iris Hebbeker

• 27.01.2025: Small Empty Cycles in Simple Drawings of K_n, Anna Hofer
  • Abstract: Given a simple drawing of a graph, a sub-drawing of a plane cycle of length k induces two connected regions of the plane. If one of the two regions does not contain any of the remaining vertices of the drawing, we call the cycle an empty plane k-cycle. In this talk, we consider simple drawings of the complete graph K_n and examine them with respect to the existence of empty plane k-cycles for small k. For k=3,4 it is known, that every vertex is incident to at least two empty plane k-cycles. We show that every vertex in a simple drawing of K_n is also incident to an empty plane k-cycle with k=5 or k=6.
    This is joint work with Joachim Orthaber, Birgit Vogtenhuber, and Alexandra Weinberger.