Paul Seymour

About

Paul Seymour is the Albert Baldwin Dod Professor of Mathematics at Princeton University, holding positions in both the Department of Mathematics and the Program in Applied and Computational Math. His research primarily focuses on discrete mathematics, with an emphasis on graph theory. He is currently working on the structure of graphs with certain induced subgraphs forbidden, and has particular interests in the Erdős-Hajnal conjecture and the various conjectures of Gyarfas about chi-boundedness. Seymour's collaborative work includes joint research with Maria Chudnovsky and Robin Thomas, and he is actively involved in organizing the Princeton Discrete Math Seminar. His professional activities also include overseeing the Barbados graph theory workshops, with records of these events spanning from 2014 to 2026.

Research topics

• Discrete mathematics
• Mathematics
• Combinatorics
• Mathematical analysis

Selected publications

• A survey of χ‐boundedness

  Journal of Graph Theory · 2020 · 140 citations

  Senior authorCorresponding

  Abstract If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? András Gyárfás made a number of challenging conjectures about this in the early 1980s, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.

  DOI

• Induced subgraphs of bounded treewidth and the container method

  Society for Industrial and Applied Mathematics eBooks · 2021 · 22 citations

  Senior authorCorresponding

  A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: the Maximum Weight Independent Set problem in long-hole-free graphs, and the Feedback Vertex Set problem in P5-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended C5 is a five-vertex hole with an additional vertex adjacent to one…

  DOI

• Induced Subgraphs of Bounded Treewidth and the Container Method

  SIAM Journal on Computing · 2024-05-31 · 7 citations

  articleSenior author

  A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By $P_t$ we denote a path on $t$ vertices. In this paper we give polynomial-time algorithms for the following problems: the Maximum Weight Independent Set problem in long-hole-free graphs, and the Feedback Vertex Set problem in $P_5$-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended $C_5$ is a five-vertex hole with an additional vertex adja…

  PublisherDOI

• A counterexample to the coarse Menger conjecture

  Journal of Combinatorial Theory Series B · 2025-02-13 · 2 citations

  articleOpen accessSenior author

  Menger's well-known theorem from 1927 characterizes when it is possible to find k vertex-disjoint paths between two sets of vertices in a graph G . Recently, Georgakopoulos and Papasoglu and, independently, Albrechtsen, Huynh, Jacobs, Knappe and Wollan conjectured a coarse analogue of Menger's theorem, when the k paths are required to be pairwise at some distance at least d . The result is known for k ≤ 2 , but we will show that it is false for all k ≥ 3 , even if G is constrained to have maximu…

  PublisherDOI

• Induced subgraph density. VI. Bounded VC-dimension

  Advances in Mathematics · 2025-10-15 · 2 citations

  articleOpen accessSenior author

  We confirm a conjecture of Fox, Pach, and Suk, that for every d > 0 , there exists c > 0 such that every n -vertex graph of VC-dimension at most d has a clique or stable set of size at least n c . This implies that, in the language of model theory, every graph definable in NIP structures has a clique or anti-clique of polynomial size, settling a conjecture of Chernikov, Starchenko, and Thomas. Our result also implies that every two-colourable tournament satisfies the tournament version of the Er…

  PublisherDOI

Recent grants

• DMS-EPRSC: Induced Subgraphs and Graph Structure

  NSF · $400k · 2022–2027

• Induced Subgraphs and Coloring

  NSF · $210k · 2018–2021

• FRG: Collaborative Research: The Four-Color Theorem and Beyond

  NSF · $283k · 2004–2008

Frequent coauthors

• Maria Chudnovsky

  191 shared

• Alex Scott

  University of Oxford

  156 shared

• Neil Robertson

  University of Edinburgh

  112 shared

• Sophie Spirkl

  University of Waterloo

  83 shared

• Robin Thomas

  Shri Jagdishprasad Jhabarmal Tibrewala University

  71 shared

• Rajan M. Thomas

  Children's Hospital of Philadelphia

  40 shared

• Nicolas Trotignon

  Laboratoire de l'Informatique du Parallélisme

  32 shared

• Alexander Schrijver

  Centrum Wiskunde & Informatica

  22 shared

Similar researchers at Princeton University

• Jianqing Fanh-119
• Pramod Viswanathh-54
• Jason Leeh-53