Research Interests
I am interested in combinatorics, in particular I like working on graph minors, graph coloring, structural graph theory, directed graphs, extremal graph theory, discrete geometry, matroids, and probabilistic methods applied to these areas. This is my full list of publications.
Selected papers
Critical edge sets in vertex-critical graphs, with E. Skottova, submitted
Small hitting sets for longest paths and cycles, with S. Norin, S. Thomassé and P. Wollan, submitted
Random independent sets in triangle-free graphs, with A. Martinsson, Forum of Mathematics, Sigma, 13:e156, 2025.
Fractional chromatic number vs. Hall ratio, Combinatorica, 45, No. 37, 2025.
Chromatic number and regular subgraphs, with B. Janzer and B. Sudakov, submitted
Topological minors in typical lifts, with M. Bucić, M. Christoph and A. Müyesser, submitted
Longest cycles in vertex-transitive and highly connected graphs, with C. Groenland, S. Longbrake, J. Turcotte and L. Yepremyan, Bulletin of the London Mathematical Society, 2025.
Improved bounds for zero-sum cycles in Z_p^d, with M. Christoph, C. Knierim and A. Martinsson, Journal of Combinatorial Theory, Series B, 173, pp. 365-373, 2025.
Shortest paths on polymatroids and hypergraphic polytopes, with J. Cardinal, Combinatorial Theory, 5(3), #3, 2025.
Optimal bounds for zero-sum cycles. I. Odd order, with R. Campbell, J. P. Gollin and K. Hendrey, Journal of Combinatorial Theory, Series B, 173, pp. 246-256, 2025.
Geometric realizations of dichotomous ordinal graphs, with M. Hoffmann, P. Angelini, S. Cornelsen, C. Haase, E. Katsanou, F. Montecchiani and A. Symvonis, Proceedings of 41st Symposium on Computational Geometry (SoCG) 2025.
Resolution of the Kohayakawa-Kreuter conjecture, with M. Christoph, A. Martinsson and Y. Wigderson, Proceedings of the London Mathematical Society, 130(1), e70013, 2025.
Complexity of polytope diameters via perfect matchings, with C. Nöbel, Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) 2025.
Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs, with A. Martinsson, Journal of Combinatorial Theory, Series B, 164, pp. 1-16, 2024.
Chromatic number is not tournament-local, with A. Girão, K. Hendrey, F. Illingworth, F. Lehner, L. Michel and M. Savery, Journal of Combinatorial Theory, Series B, 168, pp. 86-95, 2024.
Inapproximability of shortest paths on perfect matching polytopes, with J. Cardinal, Proceedings of 24th Conference on Integer Programming and Combinatorial Optimization (IPCO) 2023, Journal version appeared in Mathematical Programming, 210, pp. 147-163, 2025.
Tight bounds for divisible subdivisions, with S. Das and N. Draganić, Journal of Combinatorial Theory, Series B, 165, pp. 1-19, 2024.
Linear-size universal point sets for classes of planar graphs, with S. Felsner, H. Schrezenmaier and F. Schröder, Proceedings of 39th Symposium on Computational Geometry (SoCG) 2023.
Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant, Journal of Combinatorial Theory, Series B, 155, pp. 45-51, 2022.
Even circuits in oriented matroids, with K. Heuer and S. Wiederrecht, Combinatorial Theory, 2 (1), #3, 2022.
Oriented cycles in digraphs of large outdegree, with L. Gishboliner and T. Szabó, Combinatorica, 42, pp. 1145-1187, 2022.
Dichromatic number and forced subdivisions, with L. Gishboliner and T. Szabó, Journal of Combinatorial Theory, Series B, 153, pp. 1-30, 2022.
Edge partitions of complete geometric graphs, with O. Aichholzer, J. Obenaus, J. Orthaber, R. Paul, P. Schnider, T. Taubner and B. Vogtenhuber, Proceedings of 38th Symposium on Computational Geometry (SoCG) 2022.
Publications ordered by topic
Below you can find all my papers and preprints clustered by topic, with links to freely available pdfs.
Critical edge sets in vertex-critical graphs, with E. Skottova, submitted
Defective coloring of blowups, with S. Norin, submitted
Random independent sets in triangle-free graphs, with A. Martinsson, Forum of Mathematics, Sigma, 13:e156, 2025.
Fractional chromatic number vs. Hall ratio, Combinatorica, 45, No. 37, 2025.
Chromatic number and regular subgraphs, with B. Janzer and B. Sudakov, submitted
On the difference between the chromatic and cochromatic number, accepted to SIAM Journal on Discrete Mathematics, 2025.
Vertex-critical graphs far from edge-criticality, with A. Martinsson, Combinatorics, Probability and Computing, 34, pp. 151-157, 2024.
Chromatic number is not tournament-local, with A. Girão, K. Hendrey, F. Illingworth, F. Lehner, L. Michel and M. Savery, Journal of Combinatorial Theory, Series B, 168, pp. 86-95, 2024.
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, Invited Issue of EuroComb 2021, 103839, 2023.
Complete acyclic colorings, with S. Felsner, W. Hochstättler and K. Knauer, Electronic Journal of Combinatorics, 27(2), P2.40, 2020.
Topological minors in typical lifts, with M. Bucić, M. Christoph and A. Müyesser, submitted
Hadwiger's conjecture and topological bounds, European Journal of Combinatorics, 122, 104033, 2024.
Clustered colouring of odd-H-minor-free graphs, with R. Hickingbotham, D. Y. Kang, S. Oum and D. R. Wood, Matrix Annals 2023, Matrix Book Series, 6, 73–80, 2025.
Finding dense minors using average degree, with K. Hendrey, S. Norin and J. Turcotte, Journal of Graph Theory, 108(1), 205-223, 2024.
On the choosability of H-minor-free graphs, with O. Fischer, Combinatorics, Probability & Computing, 33(2), pp. 129-142, 2024.
Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs, with A. Martinsson, Journal of Combinatorial Theory, Series B, 164, pp. 1-16, 2024.
Odd Hadwiger for line graphs, Discrete Mathematics, 346(1), 113196, 2023.
Coloring hypergraphs with excluded minors, European Journal of Combinatorics, 120, 103971, 2024.
Improved bound for improper colorings of graphs with no odd clique minor, Combinatorics, Probability and Computing, 32(2), pp. 326-333, 2023.
Disproof of a conjecture by Woodall, Electronic Journal of Combinatorics, 29(3), P3.2, 2022.
Tight bounds for divisible subdivisions, with S. Das and N. Draganić, Journal of Combinatorial Theory, Series B, 165, pp. 1-19, 2024.
Improved lower bound for the list chromatic number of graphs with no Kt minor, Combinatorics, Probability and Computing, 31(6), pp. 1070-1075, 2022.
Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant, Journal of Combinatorial Theory, Series B, 155, pp. 45-51, 2022.
Proof of the KAMAK tree conjecture, with M. Christoph, submitted
A note on digraph splitting, with M. Christoph and K. Petrova, Combinatorics, Probability and Computing, 34(4), pp. 559-564, 2025.
Subdigraphs of prescribed size and outdegree, Journal of Graph Theory, 105(1), pp. 78-82, 2024.
Subdivisions with congruence constraints in digraphs of large chromatic number, Journal of Graph Theory, 105(1), pp. 136-143, 2024.
Heroes in orientations of chordal graphs, with P. Aboulker and G. Aubian, SIAM Journal on Discrete Mathematics, 36(4), pp. 2497-2505, 2022.
On coloring digraphs with forbidden induced subgraphs, Journal of Graph Theory, 103(2), pp. 323-339, 2023.
Colorings of oriented planar graphs avoiding a monochromatic subgraph, with H. Bergold and W. Hochstättler, Discrete Applied Mathematics, 320, pp. 81-94, 2022.
Complete directed minors and chromatic number, with T. Mészáros, Journal of Graph Theory, 101(4), pp. 623-632, 2022.
Disjoint cycles with length constraints in digraphs of large connectivity or minimum degree, SIAM Journal on Discrete Mathematics, 36(2), pp. 1343-1362, 2022.
Even circuits in oriented matroids, with K. Heuer and S. Wiederrecht, Combinatorial Theory, 2 (1), #3, 2022.
Oriented cycles in digraphs of large outdegree, with L. Gishboliner and T. Szabó, Combinatorica, 42, pp. 1145-1187, 2022.
Dichromatic number and forced subdivisions, with L. Gishboliner and T. Szabó, Journal of Combinatorial Theory, Series B, 153, pp. 1-30, 2022.
A note on coloring digraphs of large girth, Discrete Applied Mathematics, 287, pp. 62-64, 2020.
Majority colorings of sparse digraphs, with M. Anastos, A. Lamaison and T. Szabó, Electronic Journal of Combinatorics, 28(2), P2.31, 2021.
A note on graphs of dichromatic number two, Discrete Mathematics and Theoretical Computer Science, 22(4), #11, 2020.
Colouring non-even digraphs, with M. Millani and S. Wiederrecht, Electronic Journal of Combinatorics, 24(9), P4.9, 2022.
On the complexity of digraph colourings and vertex-arboricity, with W. Hochstättler and F. Schröder, Discrete Mathematics and Theoretical Computer Science, 22(1), #4, 2020.
The star dichromatic number, with Winfried Hochstättler, Discussiones Mathematicae Graph Theory, 42(1), pp. 277-298, 2022.
Geometric realizations of dichotomous ordinal graphs, with M. Hoffmann, P. Angelini, S. Cornelsen, C. Haase, E. Katsanou, F. Montecchiani and A. Symvonis, Proceedings of 41st Symposium on Computational Geometry (SoCG 2025)
Complexity of polytope diameters via perfect matchings, with C. Nöbel, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2025.
Shortest paths on polymatroids and hypergraphic polytopes, with J. Cardinal, Combinatorial Theory, 5(3), #3, 2025.
A logarithmic bound for simultaneous embeddings of planar graphs, Proceedings of 31st International Symposium on Graph Drawing and Network Visualization (GD 2023). Extended version with additonal content and detail published in Discrete & Computational Geometry, 2024.
Linear-size universal point sets for classes of planar graphs, with S. Felsner, H. Schrezenmaier and F. Schröder, Proceedings of 39th Symposium on Computational Geometry (SoCG 2023)
Inapproximability of shortest paths on perfect matching polytopes, with J. Cardinal, Proceedings of 24th Conference on Integer Programming and Combinatorial Optimization (IPCO 2023), Journal version appeared in Mathematical Programming, 210, pp. 147-163, 2025.
Edge partitions of complete geometric graphs, with O. Aichholzer, J. Obenaus, J. Orthaber, R. Paul, P. Schnider, T. Taubner and B. Vogtenhuber, Proceedings of 38th Symposium on Computational Geometry (SoCG 2022)
Coloring drawings of graphs, with C. Hertrich and F. Schröder, Electronic Journal of Combinatorics, 29(1), P1.17, 2022.
Topological drawings meet classical theorems from convex geometry, with H. Bergold, S. Felsner, M. Scheucher and F. Schröder, In Graph Drawing and Network Visualization, Proceedings GD 2020, pp. 281-294, 2020, extended journal version appeared in Discrete & Computational Geometry, 70, pp. 1121-1143, 2023.
On the average complexity of the k-level, with M. Chiu, S. Felsner, M. Scheucher, P. Schnider and P. Valtr, Journal of Computational Geometry, 11(1), pp. 493-506, 2020.
A note on universal point sets for planar graphs, with M. Scheucher and H. Schrezenmaier, In Graph Drawing and Network Visualization, Proceedings GD 2019, pp. 350-356, 2019. Journal version appeared in Journal of Graph Algorithms and Applications, 24(3), pp. 247-267, 2020.
Equiangular polygon contact representations, with S. Felsner and H. Schrezenmaier, In Graph Theoretical Concepts in Computer Science, Proceedings WG 2018, 2018.
Pentagon contact representations, with S. Felsner and H. Schrezenmaier, Electronic Journal of Combinatorics, 25(3), P3.39, 2018.
Improved bounds for zero-sum cycles in Z_p^d, with M. Christoph, C. Knierim and A. Martinsson, Journal of Combinatorial Theory, Series B, 173, pp. 365-373, 2025.
Optimal bounds for zero-sum cycles. I. Odd order, with R. Campbell, J. P. Gollin and K. Hendrey, Journal of Combinatorial Theory, Series B, 173, pp. 246-256, 2025.
Resolution of the Kohayakawa-Kreuter conjecture, with M. Christoph, A. Martinsson and Y. Wigderson, Proceedings of the London Mathematical Society, 130(1), e70013, 2025.
Size-Ramsey numbers of structurally sparse graphs, with N. Draganić, M. Kaufmann, D. Munhá Correia and K. Petrova, submitted
Zero sum cycles in complete digraphs, with T. Mészáros, European Journal of Combinatorics, 98, 103399, 2021.
Twin-width of sparse random graphs, with K. Hendrey, S. Norin and J. Turcotte, Combinatorics, Probability and Computing, 34(3), pp. 401-420, 2025.
On connectivity in random graph models with limited dependencies, with J. Lengler, A. Martinsson, K. Petrova, P. Schnider, S. Weber and E. Welzl, Proceedings of the International Conference on Randomization and Computation (RANDOM 2023) . Extended journal version published in Random Structures & Algorithms, 2024.
Exact matching: Correct parity and FPT parameterized by independence number, with N. El Maalouly and L. Wulf, Proceedings of 34th International Symposium on Algorithms and Computation, ISAAC 2023
Exact matching in graphs of bounded independence number, with N. El Maalouly, Proceedings of 47th Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Parametrised algorithms for directed modular width, with S. Wiederrecht, In Algorithms and Discrete Applied Mathematics, Proceedings CALDAM 2020, pp. 415-426, 2020.
Flip-distances between graph orientations, with O. Aichholzer, J. Cardinal, T. Huynh, K. Knauer, T. Mütze and B. Vogtenhuber, In Graph Theoretic Concepts in Computer Science, Proceedings WG 2019, pp. 120-134, 2019. Journal version appeared in Algorithmica, 83, pp. 116-143, 2021.
Small hitting sets for longest paths and cycles, with S. Norin, S. Thomassé and P. Wollan, submitted
Longest cycles in vertex-transitive and highly connected graphs, with C. Groenland, S. Longbrake, J. Turcotte and L. Yepremyan, Bulletin of the London Mathematical Society, 2025.
On an induced version of Menger's theorem, with K. Hendrey, S. Norin and J. Turcotte, Electronic Journal of Combinatorics, 31(4), No. P4.28, 2024.
Cycle lengths modulo k in expanders, with A. Martinsson, European Journal of Combinatorics, 109, 103642, 2023.
Matching theory and Barnette's conjecture, with M. Gorsky and S. Wiederrecht, Discrete Mathematics, 346(2), 113249, 2023.
Hat guessing numbers of strongly degenerate graphs, with C. Knierim and A. Martinsson, SIAM Journal on Discrete Mathematics, 37(2), pp. 1331-1347, 2023.