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)
Accepted to 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)
Combinatorics, Probability and Computing, 2023
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
