Paul D. Seymour FRS (born 26 July 1950) is a British mathematician known for his work in discrete mathematics, especially graph theory.

[citation needed] His brother Leonard W. Seymour is Professor of gene therapy at Oxford University.

Their collaboration resulted in several important joint papers over the next ten years: a proof of a conjecture of Sachs, characterising by excluded minors the graphs that admit linkless embeddings in 3-space;[pub 12] a proof that every graph that is not five-colourable has a six-vertex complete graph as a minor (the four-colour theorem is assumed to obtain this result, which is a case of Hadwiger's conjecture);[pub 13] with Dan Sanders, a new, simplified, computer based proof of the four-colour theorem;[pub 14] and a description of the bipartite graphs that admit Pfaffian orientations.

[pub 18] In 2000 Robertson, Seymour, and Thomas were supported by the American Institute of Mathematics to work on the strong perfect graph conjecture, a famous open question that had been raised by Claude Berge in the early 1960s.

[pub 21] Other important results in this period include: (with Seymour's student Sang-il Oum) fixed-parameter tractable algorithms to approximate the clique-width of graphs (within an exponential bound) and the branch-width of matroids (within a linear bound);[pub 22] and (with Chudnovsky) a proof that the roots of the independence polynomial of every claw-free graph are real.

[pub 25] The series culminated in a paper of Scott and Seymour proving that for every fixed k, every graph with sufficiently large chromatic number contains either a large complete subgraph or induced cycles of all lengths modulo k,[pub 26] which leads to the resolutions of two conjectures of Gil Kalai and Roy Meshulam connecting the chromatic number of a graph with the homology of its independence complex.

[pub 27] Most recently, the four jointly resolved the 5-cycle case of the Erdős–Hajnal conjecture, which says that every graph without an induced copy of the 5-cycle contains an independent set or a clique of polynomial size.