Journal Papers

• 1. Colouring perfect graphs with bounded clique number (with Maria Chudnovsky, Aurélie Lagoutte, and Paul Seymour), Journal of Combinatorial Theory, Series B, 122, pp. 757-775, 2017.

  2. Fast Prefix Adders for Non-Uniform Input Arrival Times (with Stephan Held), Algorithmica, 77(1), pp. 287-308, 2017.

  3. Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two (with Stephan Held), ACM Transactions on Algorithms 14(1), pp. 4:1-4:18, 2018.

  4. The sandwich problem for decompositions and almost monotone properties (with Maria Chudnovsky and Celina M. H. de Figueiredo), Algorithmica 80(12), pp.3618-3645 (2018).

  5. Even Pairs and Prism Corners in Square-Free Berge Graphs (with Maria Chudnovsky, Frédéric Maffray, and Paul Seymour), appeared online in Journal of Combinatorial Theory, Series B (2018). Corrigendum.

  6. Sandwich and probe problems for excluding paths (with Celina M. H. de Figueiredo), appeared online in Discrete Applied Mathematics (2018).

  7. Piercing axis-parallel boxes (with Maria Chudnovsky and Shira Zerbib), Electronic Journal of Combinatorics 25(1), #P1.70, 2018.

  8. Triangle-free graphs with no six-vertex induced path (with Maria Chudnovsky, Paul Seymour, and Mingxian Zhong), Discrete Mathematics 341(8), pp. 2179-2196, 2018.

  9. Caterpillars in Erdős-Hajnal (with Anita Liebenau, Marcin Pilipczuk, and Paul Seymour), appeared online in Journal of Combinatorial Theory, Series B, 2018.

  10. Entropic Matroids and Their Representations (with Emmanuel Abbe), Entropy 21(10), 948, 2019.

  11. Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable (with Maria Chudnovsky, Chun-Hung Liu, Oliver Schaudt, Nicolas Trotignon, and Kristina Vušković), Journal of Graph Theory 92 (2), 67-95, 2019.

  12. Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes (with Maria Chudnovsky, Alex Scott, and Paul Seymour), Journal of Combinatorial Theory, Series B 140, pp. 84-97, 2020. 

  13. H-colouring Pt-free graphs in subexponential time (with Carla Groenland, Karolina Okrasa, Paweł Rzążewski, Alex Scott, and Paul Seymour), appeared online in Discrete Applied Mathematics, 2019.

  14. Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs (with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour), appeared online in Journal of Graph Theory, 2020.

  15. Towards Erdős-Hajnal for graphs with no 5-hole (with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour), Combinatorica 39, pp. 983-991, 2019.

  16. A Deletion-Contraction Relation for the Chromatic Symmetric Function (with Logan Crew), appeared online in European Journal of Combinatorics, 2020.

  17. Detecting an odd hole (with Maria Chudnovsky, Alex Scott, and Paul Seymour), Journal of the ACM (JACM) 67(1), pp. 1-12, 2020.

  18. Proof of the Kalai-Meshulam conjecture (with Maria Chudnovsky, Alex Scott, and Paul Seymour), appeared online in Israel Journal of Mathematics, 2020.

  19. List-three-coloring Pt-free graphs with no induced 1-subdivision of K1,s (with Maria Chudnovsky and Mingxian Zhong), Discrete Mathematics 343 (11), 2020.

  20. Disproportionate division (with Logan Crew and Bhargav Narayanan), Bulletin of the London Mathematical Society, 2019.

  21. Approximately coloring graphs without long induced paths (with Maria Chudnovsky, Oliver Schaudt, Maya Stein, and Mingxian Zhong), Algorithmica, 2019.

  22. Short directed cycles in bipartite digraphs (with Paul Seymour), Combinatorica, 2020.

  23. List-three-coloring graphs with no induced P6 + rP3 (with Maria Chudnovsky, Shenwei Huang, and Mingxian Zhong), Algorithmica, 2021. 

  24. Pure pairs. I. Trees and linear anticomplete pairs (with Maria Chudnovsky, Alex Scott, and Paul Seymour), appeared online in Advances in Mathematics, 2020.

  25. On Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture (with Patrick Hompe, Petra Pelikanova, and Aneta Pokorna), appeared online in Discrete Mathematics.

  26. On symmetric intersecting families of vectors (with Sean Eberhard, Jeff Kahn, and Bhargav Narayanan), appeared online in Combinatorics, Probability, and Computing.

  27. A Vertex-Weighted Tutte Symmetric Function, and Constructing Graphs with Equal Chromatic Symmetric Function (with Jose Aliste-Prieto, Logan Crew, and Jose Zamora), Electronic Journal of Combinatorics, 2021.

  28. Finding an induced path that is not a shortest path (with Eli Berger and Paul Seymour), Discrete Mathematics, 2021.

  29. A note on simplicial cliques (with Maria Chudnovsky, Alex Scott, and Paul Seymour), appeared online in Discrete Mathematics, 2021. 

  30. Pure pairs. II. Excluding all subdivisions of a graph (with Maria Chudnovsky, Alex Scott, and Paul Seymour), Combinatorica, 2021. 

  31. A complete multipartite basis for the chromatic symmetric function (with Logan Crew), SIAM Journal on Discrete Math, 2021. 

  32. Finding large H-colorable subgraphs in hereditary graph classes (with Maria Chudnovsky, Jason King, Michał Pilipczuk, and Paweł Rzążewski), SIAM Journal on Discrete Math, 2021. 

  33. Modular Relations of the Tutte Symmetric Function (with Logan Crew), appeared online in Journal of Combinatorial Theory, Series A, 2021.

  34. Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs (with Joseph Cheriyan, Sepehr Hajebi, and Zishen Qu), Discrete Math, 2022. 

  35. Pure pairs. VI. Excluding an ordered tree (with Alex Scott and Paul Seymour), SIDMA, 2022.

  36. Polynomial bounds for chromatic number. II. Excluding a star-forest (with Alex Scott and Paul Seymour), appeared online, Journal of Graph Theory. 

  37. Further approximations for Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture (with Patrick Hompe), Electronic Journal of Combinatorics, 2022.

  38. Concatenating bipartite graphs (with Maria Chudnovsky, Patrick Hompe, Alex Scott, and Paul Seymour), Electronic Journal of Combinatorics, 2022. 

  39. Plethysms of Chromatic and Tutte Symmetric Functions (with Logan Crew), Electronic Journal of Combinatorics, 2022. 

  40. Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth (with Tara Abrishami, Maria Chudnovsky, and Sepehr Hajebi), Advances in Combinatorics, 2022. 

  41. Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree (with Alex Scott and Paul Seymour), Journal of Graph Theory, 2022.

  42. Polynomial bounds for chromatic number. III. Excluding a double star (with Alex Scott and Paul Seymour), Journal of Graph Theory, 2022.

  43. Complexity dichotomy for List-5-Coloring with a forbidden induced subgraph (with Sepehr Hajebi and Yanjia Li), SIDMA, 2022.

  44. Digraphs with all induced directed cycles of the same length are not dichi-bounded  (with Alvaro Carbonero, Patrick Hompe, and Benjamin Moore), Electronic Journal of Combinatorics, 2022. 

  45. A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number (with Alvaro Carbonero, Patrick Hompe, and Benjamin Moore), Journal of Combinatorial Theory, Series B, 2023. 

  46. Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs (with Aristotelis Chaniotis and Zishen Qu), Discrete Math, 2023. 

  47. Erdos-Hajnal for graphs with no 5-hole (with Maria Chudnovsky, Alex Scott, and Paul Seymour), Proceedings of the LMS, 2023.

  48. The r-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size (with Yanjia Li), Discrete Math, 2023. 

  49. Polynomial bounds for chromatic number VI. Adding a four-vertex path (with Maria Chudnovsky, Alex Scott, and Paul Seymour), European Journal of Combinatorics, Volume 110, May 2023, 103710. 

  50. Complexity of Ck-coloring in hereditary classes of graphs (with Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, and Mingxian Zhong), Information and Computation, Volume 292, June 2023, 105015.

  51. Pure pairs. IV. Trees in bipartite graphs (with Alex Scott and Paul Seymour), Journal of Combinatorial Theory, Series B, Volume 161, July 2023, Pages 120-146. 

  52. Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix (with Alex Scott and Paul Seymour), Journal of Combinatorial Theory, Series B, Volume 161, July 2023, Pages 437-464.

  53. Polynomial bounds for chromatic number VII. Disjoint holes (with Maria Chudnovsky, Alex Scott, and Paul Seymour), Journal of Graph Theory, 2023.  

  54. Pure pairs. X. Tournaments and the strong Erdos-Hajnal property (with Maria Chudnovsky, Alex Scott and Paul Seymour), European Journal of Combinatorics, 2023. 

  55. Strengthening Rodl's theorem (with Maria Chudnovsky, Alex Scott, and Paul Seymour), Journal of Combinatorial Theory, Series B, 2023.

  56. Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture (with Patrick Hompe and Zishen Qu), Discrete Mathematics, 2023. 

  57. Bipartite graphs with no K6-minor (with Maria Chudnovsky, Alex Scott, and Paul Seymour), Journal of Combinatorial Theory, Series B, 2023.

  58. Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs (with Tara Abrishami, Maria Chudnovsky, and Sepehr Hajebi), Electronic Journal of Combinatorics, 2023. 

  59.  Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree (with Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Pawel Rzazewski, and Kristina Vuskovic), Journal of Combinatorial Theory, Series B, 2023.

  60. Induced subgraphs and tree-decompositions VII. Basic obstructions in H-free graphs (with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, and Sepehr Hajebi), Journal of Combinatorial Theory, Series B, 2024. 

  61. Induced subgraphs and tree decompositions V. One neighbor in a hole (with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, and Kristina Vušković), Journal of Graph Theory, 2023. 

  62. Pure pairs. V. Excluding some long subdivision (with Alex Scott and Paul Seymour), Combinatorica, 2023.

  63. Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path (with Alex Scott and Paul Seymour), Combinatorica, 2023.

  64. Hitting all maximum stable sets in P5-free graphs (with Sepehr Hajebi and Yanjia Li), Journal of Combinatorial Theory, Series B, 2024. 

  65. Pure pairs. IX. Transversal trees (with Alex Scott and Paul Seymour), SIDMA, 2024. 

  66. Four-coloring P6-free graphs. I. Extending an excellent precoloring (with Maria Chudnovsky and Mingxian Zhong), SICOMP, 2024.

  67. Four-coloring P6-free graphs. II. Finding an excellent precoloring (with Maria Chudnovsky and Mingxian Zhong), SICOMP, 2024. 

  68. List-3-Coloring ordered graphs with a forbidden induced subgraph (with Sepehr Hajebi and Yanjia Li), SIAM Journal on Discrete Mathematics 38, no. 1: 1158-1190 , 2024.

  69. Induced subgraphs and tree decompositions VIII. Excluding a forest in (theta, prism)-free graphs (with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, and Sepehr Hajebi), Combinatorica, 2024. 

  70. Tree independence number I. Tree independence number for (even hole, diamond, pyramid)-free graphs (with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, and Kristina Vušković), Journal of Graph Theory, 2024. 

  71. Homogeneous sets in graphs and a chromatic multisymmetric function (with Logan Crew, Evan Haithcock, and Josephine Reynes), Advances in Applied Math, 2024. 

  72. List-k-Coloring H-free graphs for all k>4 (with Maria Chudnovsky, and Sepehr Hajebi), Combinatorica, 2024. 

Conference Papers

• 1. A fast algorithm for rectilinear Steiner trees with length restrictions on obstacles (with Stephan Held), in Proceedings of the 2014 on International Symposium on Physical Design, pp. 37-44. ACM, 2014.

  2. Extended abstract of Approximately coloring graphs without long induced paths (with Maria Chudnovsky, Oliver Schaudt, Maya Stein, and Mingxian Zhong), International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 193-205. Springer, Cham, 2017.

  3. Four-coloring P6-free graphs (with Maria Chudnovsky and Mingxian Zhong), in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1239-1256. Society for Industrial and Applied Mathematics, 2019.

  4. Extended abstract of Complexity of Ck-coloring in hereditary classes of graphs (with Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, and Mingxian Zhong), 27th Annual European Symposium on Algorithms, 2019.

  5. Extended abstract of Finding large H-colorable subgraphs in hereditary graph classes (with Maria Chudnovsky, Jason King, Michał Pilipczuk, and Paweł Rzążewski),  28th Annual European Symposium on Algorithms, 2020.

Preprints

• 1. Tree independence number II. Three-path configurations (with Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov), submitted. 

  2. The sandwich problem for odd-hole-free and even-hole-free graphs (with Kathie Cameron, Aristotelis Chaniotis, Celina M. H. de Figueiredo), submitted. 

  3. Graphs of bounded chordality (with Aristotelis Chaniotis, and Babak (Bobby) Miraftab), submitted. 

  4. Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth (with Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov), submitted, 2024. 

  5. On prime Caley graphs (with Maria Chudnovsky, Michal Cizek, Logan Crew, Ján Mináč, Tung T. Nguyen, and Nguyễn Duy Tân), submitted, 2023. 

  6. Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole (with Maria Chudnovsky, and Sepehr Hajebi), submitted, 2023. 

  7. Induced subgraphs and tree decompositions XIII. Basic obstructions in H-free graphs for finite H (with Bogdan Alecu, Maria Chudnovsky, and Sepehr Hajebi), submitted, 2023. 

  8. Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs (with Bogdan Alecu, Maria Chudnovsky, and Sepehr Hajebi), submitted, 2023. 

  9. Induced subgraphs and tree decompositions XI. Local structure in even-hole-free graph of large treewidth (with Bogdan Alecu, Maria Chudnovsky, and Sepehr Hajebi), submitted, 2023. 

  10. Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs (with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, and Sepehr Hajebi), submitted, 2023. 

  11. On heroes in digraphs with forbidden induced forests (with Alvaro Carbonero, Hidde Koerts, and Benjamin Moore), submitted, 2023. 

  12. Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs (with Bogdan Alecu, Maria Chudnovsky, and Sepehr Hajebi), submitted, 2023. 

  13. The Kromatic Symmetric Function: A K-theoretic Analogue of X_G (with Logan Crew, and Oliver Pechenik), submitted, 2023. 

  14. Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets (with Tara Abrishami, Maria Chudnovsky, and Sepehr Hajebi), submitted, 2022. 

  15. Pure pairs. VIII. Excluding a sparse graph (with Alex Scott and Paul Seymour), submitted, 2021.

  16. The guillotine approach for TSP with neighborhoods revisited, not submitted.

Theses

PhD thesis: Cliques, stable sets, and coloring in graphs with forbidden induced subgraphs
Advisors: Maria Chudnovsky, Paul Seymour (Princeton University)

Master's thesis: Boolean Circuit Optimization
Advisor: Stephan Held (University of Bonn)

Bachelor's thesis: The Group Steiner Tree Problem (in German)
Advisor: Stephan Held (University of Bonn)