Permanents, Pfaffian Orientations, And Even Directed Circuits (Extended Abstract) (2009)
William McCuaig, Neil Robertson, P. D. Seymour, Robin Thomas
We give a polynomial-time algorithm for the following problem of Pólya. Given an n × n 0-1 matrix, either find a matrix obtained from it by changing some of the 1’s to −1’s in such a way that...
Discrete Applied Mathematics 23 (1989) 243-265. (2009)
H. E. Rose, A Course, Number Theory, E. C. Milner, Basic Wqo, ...
[21] M. Yannakakis, "A polynomial algorithm for the min-cut linear arrangement
Neil Robertson, P. D. Seymour, Robin Thomas
Given a 0-1 square matrix A, when can some of the 1’s be changed to −1’sinsuchaway that the permanent of A equals the determinant of the modified matrix? When does a real square matrix have the...
Mathematical Programming Ser. B 97:405–422 (2003) (2009)
Maria Chudnovsky, Neil Robertson, P. D. Seymour, Robin Thomas
Abstract. Agraphisperfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The class of perfect graphs is important for several reasons. For...
DETECTING MATROID MINORS (2008)
When % is a collection of matroids, the question whether M has a minor in % can be easy or hard, depending on the choice of < 6. More precisely, the number of demands made on an...
J. Combinatorial Theory B 38(1985), 73–88. (2008)
N. Alon, N. Alon, P. D. Seymour
[3] N. Alon and V. D. Milman: λ1, isoperimetric inequalities for graphs and superconcentrators,
ARTICLE NO. doi:10.1006/jctb.2000.2031 Directed Tree-Width (2008)
Thor Johnson, Neil Robertson, P. D. Seymour, Robin Thomas
We generalize the concept of tree-width to directed graphs, and prove that every directed graph with no “haven ” of large order has small tree-width. Conversely, a digraph with a large haven has...
North-Holland GRAPHS WITH SMALL BANDWIDTH AND CUTWIDTH (2008)
We give counter-examples to the following conjecture which arose in the study of small bandwidth graphs. “For a graph G, suppose that IV(G’) ( < 1 + ci. diameter (G’) for any connected...
On Structural Description of Lower Ideals of Trees (2008)
Neil Robertson, P. D. Seymour, Robin Thomas
ABSTRACT. A lower ideal of trees is a set I of finite trees such that if T ∈ I and T topologically contains S then S ∈ I. We prove that every lower ideal of trees I has a structural description,...
Permanents, Pfaffian orientations, (2008)
Neil Robertson, P. D. Seymour, Robin Thomas
and even directed circuits
Mathematical Programming Ser. B 97:405–422 (2003) (2007)
Maria Chudnovsky, Neil Robertson, P. D. Seymour, Robin Thomas
Abstract. Agraphisperfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The class of perfect graphs is important for several reasons. For...
Maria Chudnovsky, Neil Robertson, P. D. Seymour, Robin Thomas
Partially supported by NSF grant DMS-0200595. A graph is perfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The class of perfect graphs...
On Odd Cuts and Plane Multicommodity Flows (2006)
Let T be an even subset of the vertices of a graph G. A T-cut is an edge-cutset of the graph which divides T into two odd sets. We prove that if G is bipartite, then the maximum number of disjoint...
Graph Minors. XX. Wagner’s conjecture (2004)
We prove Wagner’s conjecture, that for every infinite set of finite graphs, one of its members is isomorphic to a minor of another. 1
Permanents, Pfaffian orientations, and even directed circuits (1999)
Robertson, Neil, Seymour, P. D., Thomas, Robin
Given a 0-1 square matrix A, when can some of the 1's be changed to -1's in such a way that the permanent of A equals the determinant of the modified matrix? When does a real square matrix have the...
Non-Planar Extensions Of Planar Graphs (1999)
Neil Robertson, P. D. Seymour, Robin Thomas
A graph G is almost 4-connected if it is simple, 3-connected, has at least five vertices, and V (G) cannot be partitioned into three sets A; B; C in such a way that jCj = 3, jAj 2, jBj 2, and no edge...
Thor Johnson, Neil Robertson, P. D. Seymour, Robin Thomas
We generalize the concept of tree-width to directed graphs, and prove that every directed graph with no "haven" of large order has small tree-width. Conversely, a digraph with a large haven...
Vadim E. Zverovich, Msc C C, M. Chudnovsky, N. Robertson, P. D. Seymour, R. Thomas, ...
A subclass of perfect graphs called basic graphs plays an essential role in the announced
Girth Six Cubic Graphs Have Petersen Minors (1997)
Neil Robertson, P. D. Seymour, Robin Thomas
We prove that every 3-regular graph with no circuit of length less than six has a subgraph isomorphic to a subdivision of the Petersen graph. 3 January 1997 Revised 7 September 1997 Research...
For a review and references (1996)
Robin Thomas, N. Robertson, P. D. Seymour, Graph Minors, X. Obstructions
the graph minor theorem. Exercises 1. Prove that for n ≥ 3 the complete graph on n vertices has branch-width ⌈2n/3⌉. 2. Prove that if a graph G has a cycle, then bw(G) ≤ tw(G) + 1 ≤...
The complexity of multiterminal cuts (1994)
E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis
In the Multiterminal Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all...
The complexity of multiterminal cuts (1994)
E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis
In the Multiterminal Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all...
Linkless embeddings of graphs in 3-space (1993)
Neil Robertson, P. D. Seymour, Robin Thomas
Abstract. We announce results about flat (linkless) embeddings of graphs in 3space. A piecewise-linear embedding of a graph in 3-space is called flat if every circuit of the graph bounds a disk...
Let Σ be a (connected) surface of “complexity ” κ; that is, Σ may be obtained from a sphere by adding either 1κ handles or κ crosscaps. Let ρ ≥ 0 be an integer, and let Γ be 2 a...
Neil Robertson, P. D. Seymour, Robin Thomas
1 For every infinite cardinal κ we characterize graphs not containing a subdivision of Kκ. 2 1.
research was performed under a consulting agreement with Bellcore and while visiting
On odd cuts and plane multicommodity flows (1981)
Let T be an even subset of the vertices of a graph G. A T-cut is an edge-cutset of the graph which divides T into two odd sets. We prove that if G is bipartite, then the maximum number of...
On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte (1979)
It is well known that the Petersen graph is not 3-edge-colourable; that is, if we regard its 1-factors as (0, l)-functions on the set of edges, the constant function 1 cannot be obtained by adding...
A Note on a Combinatorial Problem of Erdos and Hajnal (1974)
A family of sets F is said by Miller [1] to have property B if there exists a set intersecting each member of F but containing no member of F. Erdos and Hajnal [2] define m(s) to be the least k for...