Photo 14.10.19, 23 29 16.jpg

Sebastian Wiederrecht

I'm a PhD student working on graph theory in the group of Stephan Kreutzer at TU Berlin.

Colouring Non-Even Digraphs

A colouring of a digraph as defined by Neumann-Lara in 1982 is a vertex-colouring such that no monochromatic directed cycles exist. The minimal number of colours required for such a colouring of a loopless digraph is defined to be its dichromatic number. This quantity has been widely studied in the last decades and can be considered as a natural directed analogue of the chromatic number of a graph. A digraph D is called even if for every 0-1-weighting of the edges it contains a directed cycle of even total weight.
We show that every non-even digraph has dichromatic number at most 2 and an optimal colouring can be found in polynomial time. We strengthen a previously known NP-hardness result by showing that deciding whether a directed graph is 2-colourable remains NP-hard even if it contains a feedback vertex set of bounded size.

Talk at Cycles and Colourings 2019

A Grid Theorem for Perfect Matching Width of Bipartite Matching Covered Graphs

A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition. It was introduced by Norine and intended as a tool for the structural study of matching covered graphs, especially in the context of Pfaffian orientations. Norine conjectured that graphs of high perfect matching width would contain a large grid as a matching minor, similar to the result on treewidth by Robertson and Seymour.
In this paper we obtain the first results on perfect matching width since its introduction. For the restricted case of bipartite graphs, we show that perfect
matching width is equivalent to directed treewidth and thus the Directed Grid Theorem by Kawarabayashi and Kreutzer for directed treewidth implies
Norine’s conjecture.

Talk at WG 2019

A Note on Directed Treewidth

We characterise digraphs of directed treewidth one in terms of forbidden butterfly minors. Moreover, we show that there is a linear relation between the hypertree-width of the dual of the cycle hypergraph of D, i. e. the hypergraph with vertices V(D) where every hyperedge corresponds to a directed cycle in D, and the directed treewidth of D. Based on this we show that a digraph has directed treewidth one if and only if its cycle hypergraph is a hypertree.

Talk at KOLKOM 2019