minors the graphs that admit linkless embeddings in 3-space; 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); with Dan Sanders, a new, simplified, computer based proof of the four-colour theorem; and a description of the bipartite graphs that admit Pfaffian orientations. In the same period, Seymour and Thomas also published several significant results: (with Noga Alon) a separator theorem for graphs with an excluded minor, extending the planar separator theorem of Richard Lipton and Robert Tarjan; a paper characterizing treewidth in terms of brambles; and a polynomial-time algorithm to compute the branch-width of planar graphs. 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. Seymour's student Maria Chudnovsky joined them in 2001, and in 2002 the four jointly proved the conjecture. Seymour continued to work with Chudnovsky, and obtained several more results about induced subgraphs, in particular (with Cornuéjols, Liu, and Vušković) a polynomial-time algorithm to test whether a graph is perfect, and a general description of all claw-free graphs. 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); and (with Chudnovsky) a proof that the roots of the independence polynomial of every claw-free graph are real. In the 2010s Seymour worked mainly on χ-boundedness and the Erdős–Hajnal conjecture. In a series of papers with Alex Scott and partly with Chudnovsky, they proved two conjectures of András Gyárfás, that every graph with bounded clique number and sufficiently large chromatic number has an induced cycle of odd length at least five, and has an induced cycle of length at least any specified number. 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, 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. There was also a polynomial-time