Recent papers of our group

Preprints and forthcoming papers

  • A Lean 4 Formalisation of OpenAI’s Proof of the Cycle Double Cover Conjecture (V. Bajpai, J. Carmesin and U. Okur), Preprint (2026); pdf
  • Stotting in positional games (J. Carmesin and Y. Mogge), Preprint (2026); pdf
  • A characterisation of all vertex-transitive finite graphs of connectivity < 5 (J. Kurkofka and T. Planken), Preprint (2026); pdf
  • A Structural Linear-Time Algorithm for Computing the Tutte Decomposition (R. Bourneuf and T. Planken), Preprint (2025); pdf
  • How Local Separators Shape Community Structure in Large Networks (S. Frenkel and J. Carmesin), Preprint (2025); pdf
  • A Recolouring Version of a Conjecture of Reed (L. De Meyer, C. Legrand-Duchesne, J. León, T. Planken and Y. Tamitegama), Preprint (2025); pdf
  • Canonical graph decompositions via local separations (R. W. Jacobs, P. Knappe and J. Kurkofka), Preprint (2025); pdf
  • Lassos: Pushing Tree Decompositions Forward Along Homomorphisms (B. M. Bumpus, J. Fairbanks and W. J. Turner), Preprint (2024); pdf
  • Towards a Stallings-type theorem for finite groups (J. Carmesin, G. Kontogeorgiou, J. Kurkofka and W. J. Turner), Preprint (2024); pdf
  • How to apply tree decomposition ideas in large networks? (J. Carmesin and S. Frenkel), accepted at IPEC; pdf
  • Shallow Hitting Edge Sets in Uniform Hypergraphs (T. Planken and T. Ueckerdt), Preprint (2023); pdf
  • Canonical graph decompositions via coverings (R. Diestel, R. W. Jacobs, P. Knappe and J. Kurkofka), to appear in Transactions of the American Mathematical Society; pdf
  • A characterisation of 3-colourable 3-dimensional triangulations (J. Carmesin, E. Nevinson and B. Saunders), Preprint (2022); pdf

2026

  • Augmenting to 4-vertex connectivity is fixed-parameter tractable (J. Carmesin and M. S. Ramanujan), SODA 2026, pages 2015–2042; pdf
  • Hardness of Planarity for Weak Temporal Sequences of 2-Connected Graphs (J. Carmesin and W. J. Turner), Theoretical Computer Science 1070 (2026), article 115825; pdf
  • A Tutte-type canonical decomposition of 3- and 4-connected graphs (J. Kurkofka and T. Planken), SODA 2026, pages 2942–3021; pdf
  • A Graph Minors Approach to Temporal Sequences (J. Carmesin and W. J. Turner), STOC 2026, pages 1388–1396; pdf
  • Embedding simply connected 2-complexes in 3-space (J. Carmesin), Memoirs of the American Mathematical Society 319 (2026), no. 1625, 82 pages; pdf
  • A representation theorem for end spaces of infinite graphs (J. Kurkofka and M. Pitz), Mathematical Proceedings of the Cambridge Philosophical Society 181(2) (2026), pages 1021–1047; pdf

2025

  • Colouring the 1-skeleton of d-dimensional triangulations (T. Planken), Innovations in Graph Theory 2 (2025), pages 275–299; pdf
  • Characterising 4-tangles through a connectivity property (J. Carmesin and J. Kurkofka), The Electronic Journal of Combinatorics 32(3) (2025), P3.26; pdf
  • Canonical decompositions of 3-connected graphs (J. Carmesin and J. Kurkofka), Advances in Combinatorics 2025:7, 73 pages; FOCS 2023, pages 1887–1920; pdf
  • On the edge-chromatic number of 2-complexes (J. Kurkofka and E. Nevinson), Discrete Mathematics 348(2) (2025), article 114309; pdf
  • Dual matroids of 2-complexes—Revisited (J. Carmesin), Bulletin of the London Mathematical Society 57(7) (2025), pages 2033–2044; pdf

2024

  • Entanglements (J. Carmesin and J. Kurkofka), Journal of Combinatorial Theory, Series B 164 (2024), pages 17–28; pdf
  • The immersion-minimal infinitely edge-connected graph (P. Knappe and J. Kurkofka), Journal of Combinatorial Theory, Series B 164 (2024), pages 492–516; pdf
  • Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets (T. Planken and T. Ueckerdt), SoCG 2024, pages 74:1–74:14; pdf
  • A Whitney type theorem for surfaces: characterising graphs with locally planar embeddings (J. Carmesin), Combinatorica 44(6) (2024), pages 1297–1323; pdf

2023

  • On Andreae's Ubiquity Conjecture (J. Carmesin), Journal of Combinatorial Theory, Series B 162 (2023), pages 68–70; pdf
  • Outerspatial 2-complexes: Extending the class of outerplanar graphs to three dimensions (J. Carmesin and T. Mihaylov), The Electronic Journal of Combinatorics 30(3) (2023), P3.20; pdf
  • Characterising graphs with no subdivision of a wheel of bounded diameter (J. Carmesin), Journal of Combinatorial Theory, Series B 161 (2023), pages 21–51; pdf

2022

  • Graph Theory - A Survey on the Occasion of the Abel Prize for László Lovász (J. Carmesin), Jahresbericht der Deutschen Mathematiker-Vereinigung 124(2) (2022), pages 83–108; pdf
  • Local 2-separators (J. Carmesin), Journal of Combinatorial Theory, Series B 156 (2022), pages 101–144; pdf
  • New Constructions related to the Polynomial Sphere Recognition Problem (J. Carmesin and L. Lichev), Discrete & Computational Geometry 67(4) (2022), pages 1097–1123; pdf
  • Canonical trees of tree-decompositions (J. Carmesin, M. Hamann and B. Miraftab), Journal of Combinatorial Theory, Series B 152 (2022), pages 1–26; pdf