#8,670

Most Influential Person

American mathematician

According to Wikipedia, Paul D. Seymour is a British mathematician known for his work in discrete mathematics, especially graph theory. He was responsible for important progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, claw-free graphs, χ-boundedness, and the Erdős–Hajnal conjecture. Many of his recent papers are available from his website.

- Graph Minors. II. Algorithmic Aspects of Tree-Width (1614)
- Graph Minors .XIII. The Disjoint Paths Problem (1247)
- Graph Minors (1045)
- Graph Minors. XX. Wagner's conjecture (800)
- Graph Minors: XV. Giant Steps (777)
- The Strong Perfect Graph Theorem (741)
- Graph minors. III. Planar tree-width (718)
- Graph minors. X. Obstructions to tree-decomposition (697)
- Graph minors. V. Excluding a planar graph (694)
- Decomposition of regular matroids (686)
- The Complexity of Multiterminal Cuts (654)
- The Four-Colour Theorem (580)
- Graph minors. I. Excluding a forest (570)
- Approximating clique-width and branch-width (472)
- Quickly Excluding a Planar Graph (448)
- Graph Searching and a Min-Max Theorem for Tree-Width (404)
- Call routing and the ratcatcher (353)
- Graph Minors. XVI. Excluding a non-planar graph (319)
- Recognizing Berge Graphs (301)
- Directed Tree-Width (275)
- Hadwiger's conjecture forK6-free graphs (267)
- Monotonicity in Graph Searching (261)
- Nowhere-zero 6-flows (237)
- The complexity of multiway cuts (extended abstract) (236)
- Percolation probabilities on the square lattice (234)
- Packing directed circuits fractionally (230)
- PERMANENTS, PFAFFIAN ORIENTATIONS, AND EVEN DIRECTED CIRCUITS (229)
- The matroids with the max-flow min-cut property (227)
- A separator theorem for graphs with an excluded minor and its applications (218)
- A separator theorem for nonplanar graphs (209)
- On Multi‐Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte (208)
- Multicommodity flows in planar graphs (205)
- Graph minors. IV. Tree-width and well-quasi-ordering (198)
- Averaging sets: A generalization of mean values and spherical designs (197)
- The structure of claw-free graphs (192)
- Tour Merging via Branch-Decomposition (192)
- Surveys in combinatorics 1985: Graph minors – a survey (183)
- Sachs' Linkless Embedding Conjecture (178)
- The roots of the independence polynomial of a clawfree graph (168)
- Disjoint paths in graphs (166)
- Packing directed circuits (165)
- Graph minors. VII. Disjoint paths on a surface (160)
- A new proof of the four-colour theorem (158)
- The Ring Loading Problem (154)
- Matroids and Multicommodity Flows (153)
- Graph minors. VIII. A kuratowski theorem for general surfaces (149)
- Graph minors XXIII. Nash-Williams' immersion conjecture (132)
- On Odd Cuts and Plane Multicommodity Flows (131)
- Efficiently four-coloring planar graphs (117)
- Matroid representation over GF(3) (112)
- Graph minors. IX. Disjoint crossed paths (109)
- Quickly excluding a forest (109)
- Excluding any graph as a minor allows a low tree-width 2-coloring (107)
- Planar Separators (104)
- Graph minors. VI. Disjoint paths across a disc (103)
- On secret-sharing matroids (98)
- Claw-free graphs. V. Global structure (97)
- Graph Minors. XI. Circuits on a Surface (94)
- Spanning trees with many leaves (94)
- The Structure of Homometric Sets (86)
- The metamathematics of the graph minor theorem (85)
- Proper minor-closed families are small (83)
- The Forbidden Minors of Binary Clutters (79)
- Recognizing graphic matroids (77)
- ON THE TWO-COLOURING OF HYPERGRAPHS (77)
- Packing Non-Zero A-Paths In Group-Labelled Graphs (72)
- On induced subgraphs of the cube (70)
- Graphs with small bandwidth and cutwidth (68)
- Claw-free graphs. IV. Decomposition theorem (67)
- Graph Minors .XII. Distance on a Surface (66)
- The three-in-a-tree problem (63)
- Characterization of even directed graphs (63)
- Disjoint Paths—A Survey (63)
- On the odd-minor variant of Hadwiger's conjecture (62)
- Graph Minors: XVII. Taming a Vortex (62)
- Excluding induced subgraphs (60)
- A survey of χ-boundedness (60)
- Bisimplicial vertices in even-hole-free graphs (59)
- A note on the production of matroid minors (59)
- On minors of non-binary matroids (58)
- Linkless embeddings of graphs in 3-space (58)
- Progress on perfect graphs (57)
- Claw-free graphs. III. Circular interval graphs (57)
- Combinatorial applications of an inequality from statistical mechanics (56)
- Tutte's Edge-Colouring Conjecture (54)
- Hadwiger's Conjecture (54)
- Induced subgraphs of graphs with large chromatic number. I. Odd holes (54)
- Graphs of bounded rank-width (53)
- Finding disjoint trees in planar graphs in linear time (53)
- On the fractional matching polytope of a hypergraph (51)
- A FORBIDDEN MINOR CHARACTERIZATION OF MATROID PORTS (50)
- Graph minors. XXI. Graphs with unique linkages (50)
- Excluding a graph with one crossing (50)
- Graph Minors. XXII. Irrelevant vertices in linkage problems (50)
- Claw-free graphs. I. Orientable prismatic graphs (48)
- A survey of linkless embeddings (48)
- Large induced degenerate subgraphs (47)
- Bounding the vertex cover number of a hypergraph (46)
- Tournaments and colouring (46)
- On Lehman's Width-Length Characterization (46)
- Claw-free graphs. II. Non-orientable prismatic graphs (45)
- On Tutte's extension of the four-colour problem (45)
- Testing branch-width (44)
- Minors of 3-Connected Matroids (44)
- Graph Structure Theory, Proceedings of a AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors held June 22 to July 5, 1991, at the University of Washington, Seattle, USA (43)
- A counterexample to the rank-coloring conjecture (42)
- Claw-free graphs VI. Colouring (42)
- A well-quasi-order for tournaments (42)
- Fractional Colouring and Hadwiger's Conjecture (40)
- Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory (40)
- Graph Minors. XIX. Well-quasi-ordering on a surface (40)
- Permanents, Pfaffian orientations, and even directed circuits (extended abstract) (39)
- Colouring series-parallel graphs (38)
- Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes (36)
- A simpler proof and a generalization of the zero-trees theorem (36)
- Cycles in dense digraphs (36)
- Hadwiger's conjecture for line graphs (35)
- Induced subgraphs of graphs with large chromatic number. XII. Distant stars (35)
- Tree-width and planar minors (35)
- Claw-free graphs. VII. Quasi-line graphs (34)
- K4-free graphs with no odd holes (34)
- Matroid minors (33)
- Coloring Locally Bipartite Graphs on Surfaces (33)
- Packing circuits in eulerian digraphs (32)
- Colouring Eulerian Triangulations (32)
- A short proof of the two-commodity flow theorem (32)
- Self-organizing sequential search and Hilbert's inequalities (32)
- Four-terminus flows (31)
- Tournament immersion and cutwidth (30)
- Extending an edge-coloring (29)
- Induced subgraphs of graphs with large chromatic number. XIII. New brooms (29)
- The edge-density for K2, t minors (28)
- Induced Subgraphs of Graphs with Large Chromatic Number IX: Rainbow Paths (28)
- Edge-disjoint paths in digraphs with bounded independence number (27)
- Detecting even holes (27)
- Spanning trees with many leaves (26)
- A counterexample to a conjecture of Schwartz (26)
- A Relative of Hadwiger's Conjecture (26)
- Disjoint paths in tournaments (25)
- Even circuits in planar graphs (25)
- Tournament minors (25)
- Perfect matchings in planar cubic graphs (25)
- Disjoint paths in graphs (24)
- Graph Miners .XIV. Extending an Embedding (24)
- A fractional version of the Erdős-Faber-Lovász conjecture (24)
- Disjoint Paths in a Planar Graph - A General Theorem (23)
- Detecting even holes (23)
- A Note on Hyperplane Generation (22)
- A two-commodity cut theorem (22)
- Even pairs in Berge graphs (22)
- Graph Minors. XVIII. Tree-decompositions and well-quasi-ordering (22)
- Excluding infinite minors (21)
- On incomparable collections of sets (21)
- Petersen Family Minors (21)
- On forbidden minors for (3) (20)
- An end-faithful spanning tree counterexample (20)
- Caterpillars in Erdős-Hajnal (20)
- Triples in Matroid Circuits (20)
- Large rainbow matchings in general graphs (19)
- Some New Results on the Well-Quasi-Ordering of Graphs (19)
- Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes (19)
- Induced Subgraphs of Graphs With Large Chromatic Number. X. Holes of Specific Residue (19)
- On the points-lines-planes conjecture (19)
- Irreducible Triangulations of Surfaces (18)
- Pure pairs. I. Trees and linear anticomplete pairs (18)
- Circular embeddings of planar graphs in nonspherical surfaces (18)
- Excluding subdivisions of infinite cliques (18)
- Packing nearly-disjoint sets (18)
- Tournament pathwidth and topological containment (18)
- Extending the Gyárfás-Sumner conjecture (18)
- Self-organizing Sequential Search and Hilbert's Inequalities (18)
- How the proof of the strong perfect graph conjecture was found (18)
- Excluding paths and antipaths (17)
- Detecting an Odd Hole (17)
- Adjacency in Binary Matroids (17)
- Subgraphs of large connectivity and chromatic number in graphs of large chromatic number (16)
- Kuratowski Chains (16)
- A survey of $\chi$-boundedness (16)
- A Note on List Arboricity (16)
- A note on a combinatorial problem of Erdős and Hajnal (16)
- Induced subgraphs of bounded treewidth and the container method (16)
- Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes (15)
- Edge-colouring eight-regular planar graphs (15)
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings (15)
- Tournaments with near-linear transitive subsets (15)
- Packing seagulls (14)
- Rao's degree sequence conjecture (14)
- Uniqueness of highly representative surface embeddings (14)
- Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures (14)
- Node Placement and Sizing for Copper Broadband Access Networks (13)
- Directed triangles in directed graphs (13)
- Spanning Trees of Different Weights (13)
- On Tutte's Characterization of Graphic Matroids (13)
- Cyclically five-connected cubic graphs (12)
- Growing Without Cloning (12)
- Packing and covering with matroid circuits (12)
- A generalization of chordal graphs (11)
- On the connectivity function of a matroid (11)
- Directed circuits on a torus (11)
- Three-edge-colouring doublecross cubic graphs (11)
- Clustered Colouring in Minor-Closed Classes (11)
- A Local Strengthening of Reed's Omega, Delta, Chi Conjecture for Quasi-line Graphs (11)
- Induced subgraphs of graphs with large chromatic number. VI. Banana trees (11)
- Non-Planar Extensions Of Planar Graphs (11)
- Proof of the Kalai-Meshulam conjecture (11)
- Trees and linear anticomplete pairs (11)
- A proof of total dual integrality of matching polyhedra (10)
- Unavoidable induced subgraphs in large graphs with no homogeneous sets (10)
- Eulerian digraph immersion (10)
- The Ring Loading Problem (10)
- Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture (10)
- A note on nongraphic matroids (10)
- Detecting Matroid Minors (10)
- Detecting an induced net subdivision (10)
- Packing Odd Paths (10)
- Excluding A Grid Minor In Planar Digraphs (10)
- Tree-chromatic number (10)
- Analyzing the performance of greedy maximal scheduling via local pooling and graph theory (9)
- Excluding infinite trees (9)
- Two Chromatic Polynomial Conjectures (9)
- Excluding Infinite Clique Minors (9)
- The smallestn-uniform hypergraph with positive discrepancy (9)
- Even-hole-free graphs still have bisimplicial vertices. (9)
- Edge-colouring seven-regular planar graphs (9)
- Towards Erdős-Hajnal for Graphs with No 5-Hole (9)
- Sparse graphs without linear anticomplete pairs (9)
- Excluding pairs of graphs (9)
- Majority Colourings of Digraphs (8)
- Colouring graphs with no odd holes (8)
- Extending partial 3-colourings in a planar graph (8)
- Induced subgraphs of graphs with large chromatic number. XI. Orientations (8)
- Domination in tournaments (7)
- Counting points in hypercubes and convolution measure algebras (7)
- Excluded minors in cubic graphs (7)
- Immersion in four-edge-connected graphs (7)
- Rooted grid minors (7)
- An end-faithful spanning tree counterexample (6)
- Certifying large branch-width (6)
- quasi-line graphs (6)
- Pure Pairs. II. Excluding All Subdivisions of A Graph (6)
- Progress on the Four-Color Theorem (6)
- Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix (6)
- Uniqueness of highly representative surface embeddings (6)
- Testing for a theta (6)
- Disjoint paths in unions of tournaments (6)
- A Petersen on a Pentagon (5)
- Finding an induced path that is not a shortest path (5)
- Forbidden structures and algorithms in graphs and digraphs (5)
- Triangle-free graphs with no six-vertex induced path (5)
- Three-colourable perfect graphs without even pairs (5)
- Disjoint Cycles in Directed Graphs on the Torus and the Klein Bottle (5)
- Polynomial bounds for chromatic number. II. Excluding a star-forest (5)
- Pure pairs. VIII. Excluding a sparse graph (5)
- Cut Coloring and Circuit Covering (5)
- Bipartite minors (5)
- Detecting a Long Odd Hole (5)
- Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs (5)
- Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree (5)
- Tutte's Three-Edge-Colouring Conjecture (5)
- Finding a Shortest Odd Hole (5)
- Wheel-free planar graphs (4)
- Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path (4)
- Long cycles in critical graphs (4)
- Pure Pairs VI: Excluding an Ordered Tree (4)
- Polynomial bounds for chromatic number. III. Excluding a double star (4)
- Colouring perfect graphs with bounded clique number (4)
- Solution of three problems of Cornuéjols (3)
- Pure pairs. IV. Trees in bipartite graphs (3)
- Three steps towards Gyárfás ’ conjecture (3)
- Detecting a long even hole (3)
- Bad news for chordal partitions (3)
- Girth six cubic graphs have Petersen minors (3)
- Criticality for multicommodity flows (3)
- Pure pairs. V. Excluding some long subdivision (3)
- Counting paths in digraphs (3)
- Graph structure theory : proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, held June 22 to July 5, 1991, with support from the National Science Foundation and the Office of Naval Research (2)
- Corrigendum to "Even pairs and prism corners in square-free Berge graphs" [J. Combin. Theory, Ser. B 131 (2018) 12-39] (2)
- Excluding the fork and antifork (2)
- Induced subgraphs of graphs with large chromatic number. XIV. Excluding a biclique and an induced tree (2)
- Small families under subdivision. (2)
- Even pairs and prism corners in square-free Berge graphs (2)
- Corrigendum to "Bisimplicial vertices in even-hole-free graphs" (2)
- Strengthening Rodl's theorem (2)
- Holes with hats and Erdős-Hajnal (2)
- A note on simplicial cliques (2)
- Extending the GyárfásSumner conjecture (2)
- Pure pairs. II. Sparse graphs without linear anticomplete pairs (2)
- Consecutive holes (2)
- Excluding a Substar and an Antisubstar (2)
- Subdivided Claws and the Clique-Stable Set Separation Property (2)
- Polynomial bounds for chromatic number VII. Disjoint holes (1)
- Proof of a conjecture of Bowlin and Brin on four-colouring triangulations (1)
- Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory (1)
- Solution of two fractional packing problems of Lovász (1)
- A Structure Theorem for Claw-Free Perfect Graphs (1)
- Polynomial bounds for chromatic number VI. Adding a four-vertex path (1)
- Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph (1)
- Induced subgraphs of graphs with large chromatic number . XII . Two-legged caterpillars (1)
- Finding balanced skew partitions in perfect graphs (1)
- Near-domination in graphs (1)
- Simplicial cliques in claw-free graphs (1)
- Pure pairs. X. Excluding six-vertex tournaments (1)
- Discharging cartwheels (1)
- Detecting an induced net subdivision (1)
- Short Directed Cycles in Bipartite Digraphs (1)
- Claw-free graphs I . Clique cutsets (1)
- Finding minimum clique capacity (1)
- Graphs with all holes the same length (1)
- Some Structural Properties of Unitary Addition Cayley Graphs (1)
- Graph Structure Theory: Proceedings of a Joint Summer Research Conference on Graph Minors Held June 22 to July 5, 1991, at the University of Washington, Seattle. Contemporary Mathematics 147 (1)
- Reducibility in the Four-Color Theorem (0)
- Pure pairs. IX. Bonsai trees (0)
- Holes with hats and Erd\H{o}s-Hajnal (0)
- Pure pairs. X. Tournaments and the strong Erdős-Hajnal property (0)
- 5-minute presentations by D. Archdeacon, E. Berger, B. Bokal, S. Cabello, R. Churchley, V. Dujmović, Z. Dvorak, K. Edwards, M. Ellingham, J. Fox, R. Fulek, G. Gauthier (0)
- Polyhedral combinatorics : proceedings of a DIMACS workshop : June 12-16, 1989 (0)
- On Packing T-Joins (0)
- 1 Hadwiger ’ s conjecture and seagulls (0)
- A letter from the editors (0)
- THE 4-COLOR PROBLEM (0)
- Concatenating bipartite graphs (0)
- ON FORBIDDEN MINORS FOR GP ( 3 ) (0)
- A pr 2 01 9 Detecting a long odd hole (0)
- 5-minute presentations by L. Postle, B. Reed, J. Rus, G. Salazar, A. Scott, P. Seymour, J. Širáň, G. Tóth, P. Whalen, D. Wood, H. Wu, M. Yancey, L. Yepremyan, L. Yuditsky, Y. Zhao (0)
- Proof of a conjecture of Plummer and Zha (0)
- Reconizing graphic matroids (0)
- Counterexample to a conjecture of Jeurissen (0)
- Pure pairs. IX. Transversal trees (0)
- Excluding a near-clique and a near-anticlique (0)
- Tournaments and colouring Citation (0)
- Long cycles in critical graphs (0)
- Solution of two fractional packing problems of lovász (0)
- C O ] 6 M ay 2 02 0 Holes with hats and (0)
- Variants of Woodall's conjecture (0)
- Even Pairs and Prism Corners in Berge Graphs (0)
- Induced Subgraphs and Subtournaments (0)
- Caterpillars in Erd\H{o}s-Hajnal (0)
- New examples of minimal non-strongly-perfect graphs (0)
- Linear representation of matroids (0)
- The Minimal Automorphism-Free Tree (0)
- Colouring graphs with no odd holes, and other stories (0)
- C O ] 1 D ec 2 01 3 BIPARTITE MINORS (0)
- 2 5 M ar 2 01 7 CYCLICALLY FIVE – CONNECTED CUBIC GRAPHS (0)
- C O ] 1 9 O ct 2 02 1 Graphs with all holes the same length (0)
- Note Note on the Production of (0)
- C O ] 2 O ct 2 01 5 Excluding A Grid Minor In Planar Digraphs (0)
- 5-minute presentations by L. Goddyn, P. Haxell, R. Kim, T. Klimosova, A. Kostochka, Z. Li, C. Liu, B. Mohar, J. Noel, S. Norin, J. Pach, M. Plumettaz, L. Postle (0)

This paper list is powered by the following services:

Paul Seymour is affiliated with the following schools:

This website uses cookies to enhance the user experience. Privacy Policy

Want to be an Academic Influence Insider?

Sign up to get the latest news, information, and rankings in our upcoming newsletter.