ETH Zürich

Dr. Raphael Steiner

Institut für Theoretische Informatik

OAT Z 29 (21st floor)

Andreasstrasse 5

8050 Zürich

Phone: +49 176 473 42551

E-Mail: raphaelmario.steiner@inf.ethz.ch

Here you can find my **CV** (last update: Mar 2024) and my **Google Scholar profile** . This is a recent **ETH-News article** about me.

Since September 2023, I am an SNSF Ambizione Fellow at ETH and principal investigator of the SNSF-funded Ambizione project/grant *Graph coloring motivated by Hadwiger's conjecture*. The project runs for 4 years, is hosted by Prof. Angelika Steger, and comes with funding for my first own PhD student at ETH, Micha Christoph. Previously, I was an ETH Zurich Postdoctoral Fellow hosted by Angelika Steger. I completed my PhD in mathematics in August 2021 at TU Berlin, under the supervision of Prof. Stefan Felsner. During this time, I was funded by a position in the DFG-research training group "Facets of Complexity".
My research interests lie in combinatorics, in particular I am interested in graph minors, graph coloring, structural graph theory, directed graphs, extremal graph theory, discrete geometry, matroid theory and probabilistic methods applied to these areas. More information can be found on my personal webpage: **LINK TO PERSONAL WEBPAGE**

**Hardness of circuit and monotone diameters of polytopes**

(with C. Nöbel)

**Resolution of the Kohayakawa-Kreuter conjecture**

(with M. Christoph, A. Martinsson and Y. Wigderson)

Submitted

**Hadwiger's conjecture and topological bounds**

Submitted

**Twin-width of sparse random graphs**

(with K. Hendrey, S. Norin and J. Turcotte)

Submitted

**Shortest paths on polymatroids and hypergraphic polytopes**

(with J. Cardinal)

Submitted

**A note on digraph splitting**

(with M. Christoph and K. Petrova)

Submitted

**On an induced version of Menger's theorem**

(with K. Hendrey, S. Norin and J. Turcotte)

Submitted

**Clustered colouring of odd-H-minor-free graphs**

(with R. Hickingbotham, D.Y. Kang, S. Oum and D. R. Wood)

Submitted

**Size-Ramsey numbers of structurally sparse graphs**

(with N. Draganić, M. Kaufmann, D. Munhá Correia and K. Petrova)

Submitted

**Finding dense minors using average degree**

(with K. Hendrey, S. Norin and J. Turcotte)

Submitted

**A logarithmic bound for simultaneous embeddings of planar graphs**

Submitted

J41. **Chromatic number is not tournament-local**

(with A. Girão, K. Hendrey, F. Illingworth, F. Lehner, L. Michel and M. Savery)
*Accepted to Journal of Combinatorial Theory, Series B, 2024*

J40. **Vertex-critical graphs far from edge-criticality**

(with A. Martinsson)
*Accepted to Combinatorics, Probability & Computing, 2024*

J39.**On connectivity in random graph models with limited dependencies **

(with J. Lengler, A. Martinsson, K. Petrova, P. Schnider, S. Weber and E. Welzl)
*Random Structures & Algorithms, 2024*

J38.**Coloring hypergraphs with excluded minors**
*European Journal of Combinatorics, 2024*

J37.**Tight bounds for divisible subdivisions**

(with S. Das and N. Draganić)
*Journal of Combinatorial Theory, Series B, 2024*

J36. **Inapproximability of shortest paths on perfect matching polytopes**

(with J. Cardinal)
*Mathematical Programming, 2023*

J35. **On the choosability of H-minor-free graphs**

(with O. Fischer)

J34. **Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs**

(with A. Martinsson)
*Journal of Combinatorial Theory, Series B, 2024*

J33. **Subdivisions with congruence constraints in digraphs of large chromatic number**
*Journal of Graph Theory, 2023*

J32. **Subdigraphs of prescribed size and outdegree**
*Journal of Graph Theory, 2023*

J31. **Hat guessing numbers of strongly degenerate graphs**

(with C. Knierim and A. Martinsson)
*SIAM Journal on Discrete Mathematics, 2023*

J30. **Coloring circle arrangements: New 4-chromatic planar graphs**

(with M.-K. Chiu, S. Felsner, M. Scheucher, F. Schröder and B. Vogtenhuber)
*European Journal of Combinatorics, 2023*

J29. **Cycle lengths modulo k in expanders**

(with A. Martinsson)
*European Journal of Combinatorics, 2023*

J28. **Matching theory and Barnette's conjecture**

(with M. Gorsky and S. Wiederrecht)
*Discrete Mathematics, 2023*

J27. **On coloring digraphs with forbidden induced subgraphs**
*Journal of Graph Theory, 2022*

J26. **Odd Hadwiger for line graphs**
*Discrete Mathematics, 2022*

J25. **Improved bound for improper colourings of graphs with no odd clique minor**
*Combinatorics, Probability and Computing, 2022*

J24. **Heroes in orientations of chordal graphs**

(with P. Aboulker and G. Aubian)
*SIAM Journal on Discrete Mathematics, 2022*

J23. **Disproof of a conjecture by Woodall**
*Electronic Journal of Combinatorics, 2022*

J22. **Improved lower bound for the list chromatic number of graphs with no K_t-minor**
*Combinatorics, Probability and Computing, 2022*

J21. **Asymptotic equivalence of Hadwiger's conjecture and its odd-minor variant**
*Journal of Combinatorial Theory, Series B, 2022*

J20. **Zero sum cycles in complete digraphs**

(with T. Mészáros)
*European Journal of Combinatorics, 2021*

J19. **Colorings of oriented planar graphs avoiding a monochromatic subgraph**

(with H. Bergold and W. Hochstättler)
*Discrete Applied Mathematics, 2022*

J18. **Complete directed minors and chromatic number**

(with T. Mészáros)
*Journal of Graph Theory, 2022*

J17. **Disjoint cycles with length constraints in digraphs of large connectivity or large minimum degree**
*SIAM Journal on Discrete Mathematics, 2022*

J16. **Even circuits in oriented matroids**

(with K. Heuer and S. Wiederrecht)
*Combinatorial Theory, 2022*

J15. **Oriented cycles in digraphs of large outdegree**

(with L. Gishboliner and T. Szabó)
*Combinatorica, 2022*

J14. **Dichromatic number and forced subdivisions**

(with L. Gishboliner and T. Szabó)
*Journal of Combinatorial Theory, Series B, 2022*

J13. **Coloring drawings of graphs**

(with C. Hertrich and F. Schröder)
*Electronic Journal of Combinatorics, 2022*

J12. **Topological drawings meet classical theorems from convex geometry**

(with H. Bergold, S. Felsner, M. Scheucher and F. Schröder)
*Discrete and Computational Geometry, 2022*

J11. **A note on coloring digraphs of large girth**
*Discrete Applied Mathematics, 2020*

J10. **On the average complexity of the k-level**

(with M. Chiu, S. Felsner, M. Scheucher, P. Schnider and P. Valtr)
*Journal of Computational Geometry, 2020*

J9. **Majority colorings of sparse digraphs**

(with M. Anastos, A. Lamaison and T.Szabó)
*Electronic Journal of Combinatorics, 2021*

J8. **A note on graphs of dichromatic number two**
*Discrete Mathematics and Theoretical Computer Science, 2021*

J7. **Complete acyclic colorings**

(with S. Felsner, W. Hochstättler and K. Knauer)
*Electronic Journal of Combinatorics, 2020*

J6. **Colouring non-even digraphs**

(with M. G. Millani and S. Wiederrecht)
*Electronic Journal of Combinatorics, 2022*

J5. **Flip distances between graph orientations**

(with O. Aichholzer, J. Cardinal, T. Huynh, K. Knauer, T. Mütze and B. Vogtenhuber)
*Algorithmica, 2021*

J4. **A note on universal point sets for planar graphs**

(with M. Scheucher and H. Schrezenmaier)
*Journal of Graph Algorithms and Applications, 2020*

J3. **On the complexity of digraph colourings and vertex arboricity**

(with W. Hochstättler and F. Schröder)
*Discrete Mathematics and Theoretical Computer Science, 2020*

J2. **The star dichromatic number**

(with W. Hochstättler)
*Discussiones Mathematicae Graph Theory, 2022*

J1. **Pentagon contact representations**

(with S. Felsner and H. Schrezenmaier)
*Electronic Journal of Combinatorics, 2018*

C16. **Exact matching: Correct parity and FPT parameterized by independence number**

(with N. El Maalouly and L. Wulf)
*34th International Symposium on Algorithms and Computation, ISAAC 2023*

C15. **A logarithmic bound for simultaneous embeddings of planar graphs**
*31st International Symposium on Graph Drawing and Network Visualization, GD 2023*

C14. **On connectivity in random graph models with limited dependencies **

(with J. Lengler, A. Martinsson, K. Petrova, P. Schnider, S. Weber and E. Welzl)
*International Conference on Randomization and Computation, RANDOM 2023*

C13. Linear-size universal point sets for classes of planar graphs

(with S. Felsner, H. Schrezenmaier and F. Schröder)
*39th Symposium on Computational Geometry, SoCG 2023*

C12. **Inapproximability of shortest paths on perfect matching polytopes**

(with J. Cardinal)
*24th Conference on Integer Programming and Combinatorial Optimization, IPCO 2023*

C11. **Exact matching in graphs of bounded independence number**

(with N. El Maalouly)
*Symposium on Mathematical Foundations of Computer Science, MFCS 2022*

C10. **Edge partitions of complete geometric graphs**

(with O. Aichholzer, J. Obenaus, J. Orthaber, R. Paul, P. Schnider, T. Taubner and B. Vogtenhuber)
*Symposium on Computational Geometry, SoCG 2022*

C9. **Coloring circle arrangements: New 4-chromatic planar graphs**

(with M.-K. Chiu, S. Felsner, M. Scheucher, F. Schröder and B. Vogtenhuber)
*Proceedings EUROCOMB 2021*

C8. **Strongly Pfaffian graphs**

(with M. Gorsky and S. Wiederrecht)
*Proceedings EUROCOMB 2021*

C7. **Topological drawings meet classical theorems from convex geometry**

(with H. Bergold, S. Felsner, M. Scheucher and F. Schröder)
*Graph Drawing and Network Visualization, Proceedings Graph Drawing 2020*

C6. **Parametrized algorithms for directed modular width**

(with Sebastian Wiederrecht)
*Algorithms and Discrete Applied Mathematics, Proceedings CALDAM 2020*

C5. **Colouring non-even digraphs**

(with M. G. Millani and Sebastian Wiederrecht)
*Proceedings EUROCOMB 2019*

C4. **A note on universal point sets for planar graphs**

(with M. Scheucher and H. Schrezenmaier)
*Graph Drawing and Network Visualization, Proceedings GD 2019*

C3. **Flip distances between graph orientations**

(with O. Aichholzer, J. Cardinal, T. Huynh, K. Knauer, T. Mütze and B. Vogtenhuber)
*Graph Theoretical Concepts in Computer Science, Proceedings WG 2019*

C2. **Equiangular polygon contact representations**

(with S. Felsner and H. Schrezenmaier)
*Graph Theoretical Concepts in Computer Science, Proceedings WG 2018*

C1. **Pentagon contact representations**

(with S. Felsner and H. Schrezenmaier)
*Proceedings EUROCOMB 2017*

**Cycle structure and colorings of directed graphs**

PhD thesis, Technical University Berlin, 2021, under the supervision of Prof. Dr. Stefan Felsner

**Neumann-Lara Flows and the Two Colour Conjecture**

Master thesis, University of Hagen, 2018, under the supervision of Prof. Dr. Winfried Hochstättler

**Existenz und Konstruktion von Dreieckszerlegungen triangulierter Graphen und Schnyder Woods**

Bachelor thesis, University of Hagen, 2016, under the supervision of Prof. Dr. Winfried Hochstättler