Sophie Spirkl

Program for Applied and Computational Mathematics
Fine Hall, Washington Road
Princeton, NJ 08544


I am a PhD student at Princeton University, and my advisors are Maria Chudnovsky and Paul Seymour. This year, I am being supported by a Charlotte Elizabeth Procter Fellowship. My CV is available here.

Open Problem Collections

Barbados 2016 (html, pdf), Barbados 2017 (html, pdf), Banff 2017 (pdf).

Publications and Preprints

  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), accepted for ACM Transactions on Algorithms.
  4. 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.
  5. Approximately coloring graphs without long induced paths (with Maria Chudnovsky, Oliver Schaudt, Maya Stein, and Mingxian Zhong), submitted, conference version in International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 193-205. Springer, Cham, 2017.
  6. Sparse graphs without linear anticomplete pairs (with Maria Chudnovsky, Alex Scott, and Paul Seymour), manuscript, 2017.
  7. Caterpillars in Erdős-Hajnal (with Anita Liebenau, Marcin Pilipczuk, and Paul Seymour), submitted.
  8. Triangle-free graphs with no six-vertex induced path (with Maria Chudnovsky, Paul Seymour, and Mingxian Zhong), submitted.
  9. 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ć), submitted.
  10. Sandwich and probe problems for excluding paths (with Celina M. H. de Figueiredo), submitted.
  11. Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes, (with Maria Chudnovsky, Alex Scott, and Paul Seymour), submitted.
  12. Piercing axis-parallel boxes (with Maria Chudnovsky and Shira Zerbib), submitted.
  13. The sandwich problem for decompositions and almost monotone properties (with Maria Chudnovsky and Celina M. H. de Figueiredo), submitted.
  14. Even Pairs and Prism Corners in Square-Free Berge Graphs (with Maria Chudnovsky, Frédéric Maffray, and Paul Seymour), submitted.
  15. The guillotine approach for TSP with neighborhoods revisited, submitted.


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