Geometry Seminar

---

Coloring Mixed Interval Graphs

Speaker: Alexander Wolff, University of Würzburg

Location: Online

Videoconference link: https://youtu.be/I6dvoyVzlQI

Date: Tuesday, December 9, 2025, 2 p.m.

Synopsis:

An interval graph is the intersection graph of a set of intervals. A mixed interval graph is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where the direction of the arcs is defined by the geometry of intervals; for example, by containment.

A proper k-coloring of a general mixed graph G is a mapping of the vertices of G to the numbers {1,2,...,k} such that (i) vertices u and v receive different colors if G contains the edge {u,v}, and (ii) vertex u receives a smaller color than v if G contains the arc (u,v).

Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020]. Coloring of mixed interval graphs shows up in the Sugiyama framework used for drawing directed graphs [Zink et al., 2022].

In my talk, I will define three classes of mixed interval graphs. For each class, I will present an exact or approximation algorithm for coloring graphs from the class (given an interval representation) with the smallest number of colors.

This is based on joint work with F. Mittelstädt, G. Gutowski, K. Junosza-Szaniawski, F. Klesen, I. Rutter, P. Rzążewski, J. Spoerhase, and J. Zink [GD 2022, ISAAC 2023].

Notes:

On Zoom.  Please contanct Boris Aronov to be put on the email announcement list and obtain Zoom details.