Coloring planar graphs with triangles far apart (2009)
Dvorak, Zdenek, Kral, Daniel, Thomas, Robin
We settle a problem of Havel by showing that there exists an absolute constant d such that if G is a planar graph in which every two distinct triangles are at distance at least d, then G is...
Color-Critical Graphs Have Logarithmic Circumference (2009)
A graph G is k-critical if every proper subgraph of G is (k-1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least log...
Threecoloring triangle-free planar graphs in linear time (2009)
Ken-ichi Kawarabayashi, Robin Thomas
Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to...
Coloring triangle-free graphs on surfaces. Extended abstract. (2009)
Gimbel and Thomassen asked whether 3-colorability of a triangle-free graph drawn on a fixed surface can be tested in polynomial time. We settle the question by giving a linear-time algorithm for...
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...
EIDMA MINICOURSE ON STRUCTUAL GRAPH THEORY (2009)
LECTURE 7: Matching structure, Pfaffian orientations and digraph structure I Topics: Edmonds ’ matching theorem, the linear hull of perfect matchings, the matching structure: decomposition into...
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...
Topics: History, equivalent formulations and an outline of a proof. What are the prospects for finding a computer-free proof? Recommended reading: [1, 2, 3]
EIDMA MINICOURSE ON STRUCTUAL GRAPH THEORY (2008)
Hadwiger’s conjecture. Jorgensen’s conjecture. Extremal problems for minors. Linkages.
Voting in agreeable societies (2008)
Berg, Deborah E., Norine, Serguei, Su, Francis Edward, Thomas, Robin, Wollan, Paul
When can a majority of voters find common ground, that is, a position they all agree upon? How does the shape of the political spectrum influence the outcome? When mathematical objects have a social...
EIDMA MINICOURSE ON STRUCTUAL GRAPH THEORY (2008)
Topics: Path-width, tree-width and applications to structure theory and the design of algorithms. The concept of a haven (bramble) as an obstacle to low tree-width and its use. Excluding a planar...
Hamilton Paths in Toroidal Graphs (2008)
Robin Thomas, Xingxing Yu, Wenan Zang
Tutte has shown that every 4-connected planar graph contains a Hamilton cycle. Grünbaum and Nash-Williams independently conjectured that the same is true for toroidal graphs. In this paper, we prove...
Set intersections, perfect graphs, and voting in agreeable societies (2008)
Deborah E. Berg, Serguei Norine, Francis Edward Su, Robin Thomas, Paul Wollan
My idea of an agreeable person is a person who agrees with me.
Christopher Carl Heckman, Robin Thomas
Abstract: We prove that every triangle-free planar graph on n vertices with maximum degree three has an independent set with size at least 3 8n. This was suggested and later conjectured by Albertson,...
Generation of simple quadrangulations of the sphere (2008)
Gunnar Brinkmann, Catherine Greenhill, Robin Thomas, Sam Greenberg, Brendan D. Mckay, Paul Wollan
Published in Discrete Math. 305 (2005), 33–54. This corrects a small error in the
Hamilton Paths in Toroidal Graphs (2008)
Robin Thomas, Xingxing Yu, Wenan Zang
Tutte has shown that every 4-connected planar graph contains a Hamilton cycle. Grünbaum and Nash-Williams independently conjectured that the same is true for toroidal graphs. In this paper, we prove...
PFAFFIAN LABELINGS AND SIGNS OF EDGE COLORINGS (2008)
Abstract. We relate signs of edge-colorings (as in classical Penrose’s result) with “Pfaffian labelings”, a generalization of Pfaffian orientations, whereby edges are labeled by elements of an...
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...
Hamilton Paths in Toroidal Graphs (2008)
Robin Thomas, Xingxing Yu, Wenan Zang
Tutte has shown that every 4-connected planar graph contains a Hamilton cycle. Grünbaum and Nash-Williams independently conjectured that the same is true for toroidal graphs. In this paper, we prove...
MINOR-MINIMAL PLANAR GRAPHS OF EVEN BRANCH-WIDTH (2008)
Abstract. Let k ≥ 1 be an integer, let H be a minor-minimal graph in the projective plane such that every homotopically non-trivial closed curve intersects H at least k times, and let G be the...
Three-coloring Klein bottle graphs of girth five (2008)
We prove that every graph of girth at least five which admits an embedding in the Klein bottle is 3-colorable. This solves a problem raised by Woodburn, and complements a result of Thomassen who...
Packing directed circuits exactly (2008)
ABSTRACT. We give an “excluded minor ” and a “structural ” characterization of digraphs that have the prop-, the maximum number of disjoint circuits in is equal to the minimum erty that for...
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
Abstract. A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. A brick is minimal if for every edge e the deletion of e...
EIDMA MINICOURSE ON STRUCTUAL GRAPH THEORY (2008)
LECTURE 4: Excluded minor theorems and well-quasi-ordering. Topics: Seymour’s splitter theorem and its applications. Analogues for higher connectivity and their applications. Separators. Typical...
An improved linear edge bound for graph linkages (2008)
A graph is said to be k-linked if it has at least 2k vertices and for every sequence s1,..., sk, t1,..., tk of distinct vertices there exist disjoint paths P1,..., Pk such that the ends of Pi are si...
On minimally non-Pfaffian graphs (2008)
Abstract. We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp...
Generation of simple quadrangulations of the sphere (2008)
Gunnar Brinkmann, Catherine Greenhill, Robin Thomas, Sam Greenberg, Brendan D. Mckay, Paul Wollan
A simple quadrangulation of the sphere is a finite simple graph embedded on the sphere such that every face is bounded by a walk of 4 edges. We consider the following classes of simple...
PFAFFIAN LABELINGS AND SIGNS OF EDGE COLORINGS (2008)
Abstract. We relate signs of edge-colorings (as in classical Penrose’s result) with “Pfaffian labelings”, a generalization of Pfaffian orientations, whereby edges are labeled by elements of an...
Three-coloring triangle-free planar graphs in linear time (2008)
Zdenek Dvorak, Ken-ichi Kawarabayashi, Robin Thomas
Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to...
Edge-Coloring Series-Parallel Multigraphs (2007)
Cristina G. Fernandes, Paulo Brazil, Robin Thomas
We give a simpler proof of Seymour's Theorem on edge-coloring series-parallel multigraphs and derive a linear-time algorithm to check whether a given series-parallel multigraph can be colored...
Edge-Coloring Series-Parallel Multigraphs (2007)
Cristina G. Fernandes, Paulo Brazil, Robin Thomas
We give a simpler proof of Seymour's Theorem on edge-coloring series-parallel multigraphs and derive a linear-time algorithm to check whether a given series-parallel multigraph can be colored...
Three-coloring Klein bottle graphs of girth five (2007)
We prove that every graph of girth at least five which admits an embedding in the Klein bottle is 3-colorable. This solves a problem raised by Woodburn, and complements a result of Thomassen who...
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...
Temperley-Lieb algebras and the Four-Color Theorem, manuscript (2007)
kauf fmanui c. edu and
Packing directed circuits exactly (2007)
ABSTRACT. We give an "excluded minor " and a "structural " characterization of digraphs D that have the property that for every subdigraph H of D, the maximum...
Generation of Simple Quadrangulations of the Sphere (2007)
Gunnar Brinkmann Faku, Catherine Greenhill, Robin Thomas, Sam Greenberg, Brendan D. Mckay, ...
A simple quadrangulation of the sphere is a finite simple graph embedded on the sphere such that every face is bounded by a walk of 4 edges. We consider the following classes of simple...
Coloring even-faced graphs in the torus and the Klein bottle (2007)
We prove that a triangle-free graph drawn in the torus with all faces bounded by even walks is 3-colorable if and only if it has no subgraph isomorphic to the Cayley graph C(Z13; 1, 5). We also prove...
The Extremal Function for 3-linked Graphs (2007)
A graph is k-linked if for every set of 2k distinct vertices {s1,..., sk, t1,..., tk} there exist disjoint paths P1,..., Pk such that the endpoints of Pi are si and ti. We prove every 6-connected...
Six-Critical Graphs on the Klein bottle Extended Abstract (2007)
Nathan Chenette, Ken-ichi Kawarabayashi, Daniel Král, Jan Kynčl, Luke Postle, Noah Streib, ...
We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list. This answers a question of...
Approved by: Maximum Codes with the Identifiable Parent Property (2006)
Dr. Xingxing Yu Advisor, Dr. Luca Dieci, Tom Trotter, Michael Lacey, Prasad Tetali, ...
To my parents, my brothers and my husband. iii ACKNOWLEDGEMENTS There are many I would like to thank for helping me get this far. First and foremost are my family who carried the burden of supporting...
The strong perfect graph theorem (2006)
Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is an odd cycle of...
The strong perfect graph theorem (2006)
Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is an odd cycle of...
The strong perfect graph theorem (2006)
Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is an odd cycle of...
Deborah E. Berg, Serguei Norine, Francis Edward Su, Robin Thomas
My idea of an agreeable person is a person who agrees with me.
The circular chromatic index of flower snarks (2006)
Mohammad Ghebleh, Serguei Norine, Daniel Král, Robin Thomas
We determine the circular chromatic index of flower snarks, by showing that χ ′ c(F3) = 7/2, χ ′ c(F5) = 17/5 and χ ′ c(Fk) = 10/3 for every odd integer k ≥ 7, where Fk denotes the flower...
The circular chromatic index of flower snarks (2006)
Mohammad Ghebleh, Daniel Král, Serguei Norine, Robin Thomas
We determine the circular chromatic index of flower snarks, by showing that χ ′ c(F3) = 7/2, χ ′ c(F5) = 17/5 and χ ′ c(Fk) = 10/3 for every odd integer k ≥ 7, where Fk denotes the flower...
Approved by: CUTTING PLANES FOR LARGE MIXED INTEGER PROGRAMMING MODELS (2006)
G. Goycoolea, William J. Cook, George L. Nemhauser, Ellis L. Johnson, Robin Thomas, Zonghao Gu
Title from box.
Serguei Norine, Paul Seymour, Robin Thomas, Paul Wollan
We prove that for every proper minor-closed class I of graphs there exists a constant c such that for every integer n the class I includes at most n!c n graphs with vertex-set {1, 2,..., n}. This...
The Extremal Function for K9 Minors (2005)
We prove that every (simple) graph on n ≥ 9 vertices and at least 7n − 27 edges either has a K9 minor, or is isomorphic to K2,2,2,3,3, or is isomorphic to a graph obtained from disjoint copies of...
Serguei Norine, Paul Seymour, Robin Thomas, Paul Wollan
We prove that for every proper minor-closed class I of graphs there exists a constant c such that for every integer n the class I includes at most n!c n graphs with vertex-set {1, 2,..., n}. This...
Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan
We prove that every sufficiently big 6-connected graph of bounded treewidth either has a K6 minor, or has a vertex whose deletion makes the graph planar. This is a step toward proving that the same...
Computer printout.
A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building...
Large induced forests in sparse graphs (2001)
Noga Alon, Dhruv Mubayi, Robin Thomas
For a graph G, leta(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree ∆. Our results include: (a) if...
Large induced forests in sparse graphs (2001)
Noga Alon, Dhruv Mubayi, Robin Thomas
For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree ∆. Our results include: (a)...
A New Proof Of The Independence Ratio Of Triangle-Free Cubic Graphs (2001)
Christopher Carl Heckman, Robin Thomas
: Staton proved that every triangle-free graph on n vertices with maximum degree three has an independent set of size at least 5n/14. A simpler proof was found by Jones. We give a yet simpler proof,...
K4-free graphs with no odd holes (2001)
Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
K4-free graphs with no odd hole and no odd antihole are three-colourable, but what about K4-free graphs with no odd hole? They are not necessarily three-colourable, but we prove a conjecture of Ding...
Large Induced Forests in Sparse Graphs (2000)
Noga Alon, Dhruv Mubayi, Robin Thomas
For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree \Delta. Our results include:...
Temperley-Lieb Algebras And The Four-Color Theorem (2000)
The Temperley-Lieb algebra T n with parameter 2 is the associative algebra over Q generated by 1; e 0 ; e 1 ; : : : ; e n , where the generators satisfy the relations e 2 i = 2e i , e i e j e i = e i...
Graph Planarity and Related Topics (1999)
This compendium is the result of reformatting and minor editing of the author's transparencies for his talk delivered at the conference. The talk covered Euler's Formula, Kuratowski's Theorem, linear...
On possible counterexamples to Negami's planar cover conjecture (1999)
A simple graph H is a cover of a graph G if there exists a mapping ϕ from H onto G such that ϕ maps the neighbors of every vertex v in H bijectively to the neighbors of ϕ(v) in G. Negami...
A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building...
EXCLUDING MINORS IN NONPLANAR GRAPHS OFGIRTHATLEASTFIVE (1999)
Robin Thomas, Jan Mcdonald Thomson
Agraphisquasi 4-connected if it is simple, 3-connected, has at least five vertices, and for every partition (A, B, C) ofV(G)either|C|≥4, or G has an edge with one end in A and the other end in B,...
On possible counterexamples to Negami's planar cover conjecture, manuscript (1999)
Abstract. A simple graph H is a cover of a graph G if there exists a mapping ' from H onto G such that ' maps the neighbors of every vertex v in H bijectively to the neighbors of '(v)...
List edge-colorings of series-parallel graphs (1999)
Abstract. It is proved that for every integer k 3, for every (simple) series-parallel graph G with maximum degree at most k, and for every collection (L(e) : e 2 E(G)) of sets, each of size at least...
On possible counterexamples to Negami's planar cover conjecture, manuscript (1999)
Abstract. A simple graph H is a cover of a graph G if there exists a mapping ' from V (H) onto V (G) such that for every vertex v of G, ' maps the neighbors of v in H bijectively to the...
List Edge-Colorings of Series-Parallel Graphs (1999)
Martin Juvan, Bojan Mohar, Robin Thomas
It is proved that for every integer k 3, for every (simple) series-parallel graph G with maximum degree at most k, and for every collection (L(e) : e 2 E(G)) of sets, each of size at least k, there...
List Edge-Colorings of Series-Parallel Graphs (1999)
Martin Juvan, Bojan Mohar, Robin Thomas
It is proved that for every integer k # 3, for every (simple) series-parallel graph G with maximum degree at most k, and for every collection (L(e):e# E(G)) of sets, each of size at least k, there...
Graph Planarity and Related Topics (1999)
. This compendium is the result of reformatting and minor editing of the author's transparencies for his talk delivered at the conference. The talk covered Euler's Formula,...
Generating Internally Four-Connected Graphs (1999)
Thor Johnson, Robin Thomas, Or H
A graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges. A graph G is internally 4-connected if it is simple, 3-connected, has at least five...
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...
Excluding Minors In Nonplanar Graphs Of Girth At Least Five (1999)
Robin Thomas, Jan Mcdonald Thomson
We show that any nonplanar graph with minimum degree at least three and no cycle of length less than five has a minor isomorphic to P \Gamma 10 , the Petersen graph with one edge deleted. We deduce...
On Possible Counterexamples to Negami's Planar Cover Conjecture (1999)
. A simple graph H is a cover of a graph G if there exists a mapping ' from V (H) onto V (G) such that for every vertex v of G, ' maps the neighbors of v in H bijectively to the neighbors...
List Edge-Colorings of Series-Parallel Graphs (1999)
Martin Juvan, Bojan Mohar, Robin Thomas
. It is proved that for every integer k 3, for every (simple) series-parallel graph G with maximum degree at most k, and for every collection (L(e) : e 2 E(G)) of sets, each of size at least k, there...
The Temperley-Lieb algebra Tn with parameter 2 is the associative algebra over Q generated by 1,e0,e1,...,en, where the generators satisfy the relations e2 i =2ei,eiejei =eiif |i − j | =1andeiej...
Recent Excluded Minor Theorems for Graphs (1999)
Summary Agraphisaminor of another if the first can be obtained from a subgraph of the second by contracting edges. An excluded minor theorem describes the structure of graphs with no minor isomorphic...
Bruce Reed, Equipe Combinatoire Cnrs, Place Jussieu, Robin Thomas
AgraphHis a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t ≥ 1beaninteger,andletGbe a graph on n vertices with no minor isomorphic to Kt+1. Kostochka...
Clique Minors In Graphs And Their Complements (1998)
A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t 1 be an integer, and let G be a graph on n vertices with no minor isomorphic to K t+1 ....
Three-Coloring Klein Bottle Graphs Of Girth Five (1998)
We prove that every graph of girth at least five which admits an embedding in the Klein bottle is 3-colorable. This solves a problem raised by Woodburn, and complements a result of Thomassen who...
An Update on the Four-Color Theorem (1998)
this article I concentrate on recent developments: equivalent formulations, a new proof, and progress on some generalizations.
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...
An Update On The Four-Color Theorem (1998)
This article appeared in Notices Amer. Math. Soc. 45 (1998), 848--859. Every planar map of connected countries can be colored using four colors in such a way that countries with a common boundary...
Excluding a Countable Clique (1998)
Reinhard Diestel, Robin Thomas
We extend the excluded K n minor theorem of Robertson and Seymour to infinite graphs, and deduce a structural characterization of the infinite graphs that have no K #0 minor. The latter is a...
An update on the Four-Color Theorem (1998)
Every planar map of connected countries can be colored using four colors in such a way that countries with a common boundary segment (not just a point) receive different colors. It is amazing that...
An update on the Four-Color Theorem (1998)
93-1-0325. This article appeared in Notices Amer. Math. Soc. 45 (1998), 848–859. Every planar map of connected countries can be colored using four colors in such a way that countries with a common...
Planarity In Linear Time (Class notes) (1997)
I give a self-contained exposition of a linear-time planarity algorithm of Shih and Hsu. 20 December 1995 Revised 6 June 1997 Partially supported by NSF under Grant No. DMS-9303761 and by ONR under...
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...
Permanents, Pfaffian Orientations, And Even Directed Circuits (Extended Abstract) (1997)
Eglinton St, Burnaby B. C, Neil Robertson, ...
) William McCuaig 5268 Eglinton St. Burnaby, B.C. Canada V5G 2B2 Neil Robertson 1 Department of Mathematics Ohio State University 231 W. 18th Ave. Columbus, Ohio 43210, USA P. D. Seymour Bellcore 445...
A graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges. A graph G is internally 4-connected if it is simple, 3-connected, has at least five...
Neil Robertson, Paul Seymour, Robin Thomas
DMS-8903132, and partially performed under a consulting agreement with Bellcore.
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 ≤...
Spanning paths in infinite planar graphs (1996)
Nathaniel Dean, Robin Thomas, Xingxing Yu
Let G be a 4-connected infinite planar graph such that the deletion of any finite set of vertices of G results in at most one infinite component. We prove a conjecture of Nash-Williams that G has a...
A new proof of the four-colour theorem (1996)
Neil Robertson, Daniel P. Sanders, Paul Seymour, Robin Thomas
(Communicated by Ronald Graham) Abstract. The four-colour theorem, that every loopless planar graph admits a vertex-colouring with at most four different colours, was proved in 1976 by Appel and...
Tree-Decompositions Of Graphs (lecture notes) (1996)
Robin Thomas, A. Preliminaries
Tree-decompositions of graphs play an important role in graph structure theory, in the theory of algorithms and in practical computation. These notes survey the first two aspects. Revised 3 June 1996...
Bruce Reed, Equipe Combinatoire, Place Jussieu, Neil Robertson, Paul Seymour, ...
92-J-1965, and partially performed under a consulting agreement with Bellcore.
Five-Connected Toroidal Graphs Are Hamiltonian (1996)
We prove that every edge in a 5-connected graph embedded in the torus is contained in a Hamilton cycle. Our proof is constructive and implies a polynomial time algorithm for finding a Hamilton cycle....
A new proof of the four-colour theorem (1996)
Neil Robertson, Daniel P. Sanders, Paul Seymour, Robin Thomas
(Communicated by Ronald Graham) Abstract. The four-colour theorem, that every loopless planar graph admits a vertex-colouring with at most four different colours, was proved in 1976 by Appel and...
Let p = p(n) be a function of n with 0 < p < 1. We consider the random graph model G(n, p); that is, the probability space of simple graphs with vertex–set {1, 2,..., n} where two distinct...
Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas, N. Robertson
Abstract. The four-colour theorem, that every loopless planar graph admits a vertex-colouring with at most four different colours, was proved in 1976 by Appel and Haken, using a computer. Here we...
Let k be an integer. A graph G is k-arrangeable (concept introduced by Chen and Schelp) if the vertices of G can be numbered v1, v2,..., vn in such a way that for every integer i with 1 ≤ i ≤ n,...
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...
Hadwiger’s conjecture for K6-free graphs (1993)
Neil Robertson, Paul Seymour, Robin Thomas
was carried out partially under a consulting agreement with Bellcore. In 1943, Hadwiger made the conjecture that every loopless graph not contractible to the complete graph on t + 1 vertices is...
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...
Hanno Lefmann, Vojtěch Rödl, Robin Thomas
Let l and k be positive integers, and let X = {0, 1,..., l k−1}. Is it true that for every coloring δ: X × X → {0, 1,...} there either exist elements x0 < x1 <... < xl of X with δ(x0,...
Bogdan Oporowski, James Oxley, Robin Thomas
Fund through the Board of Regents. We prove that, for every positive integer k, there is an integer N such that every 3-connected graph with at least N vertices has a minor isomorphic to the k-spoke...
A separator theorem for graphs with an excluded minor and its applications (1990)
Noga Alon, Paul Seymour, Robin Thomas
Let G be an n-vertex graph with nonnegative weights whose sum is 1 assigned to its vertices, and with no minor isomorphic to a given h-vertex graph H. We prove that there is a set X of no more than h...
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
A graph G has tree-width at most w if it admits a tree-decomposition of width ≤ w. It is known that once we have a tree-decomposition of a graph G of bounded width, many NP-hard problems can be...
A hypergraph H has tree-width k (a notion introduced by Robertson and Seymour) if k is the least integer such that H admits a tree-decomposition of tree-width k. We prove a compactness theorem for...
Independent Sets In Triangle-Free Cubic Planar Graphs
Christopher Carl Heckman, Robin Thomas
: We prove that every triangle-free planar graph on n vertices with maximum degree three has an independent set with size at least 3 8 n. This was suggested and later conjectured by Albertson,...
Independent Sets In Triangle-Free Cubic Planar Graphs
Christopher Carl Heckman, Robin Thomas
: We prove that every triangle-free planar graph on n vertices with maximum degree three has an independent set with size at least 3 8 n. This was suggested and later conjectured by Albertson,...
Independent Sets In Triangle-Free Cubic Planar Graphs
Christopher Carl Heckman, Robin Thomas
: Albertson, Bollobas, and Tucker conjectured in 1976 that every triangle-free cubic planar graph on v vertices has an independent set of size at least sv, for some s > 1 / 3 , with s possibly as...
Recent Excluded Minor Theorems
We discuss splitter theorems for internally 4-connected graphs and for cyclically 5-connected cubic graphs, the graph minor theorem, linkless embeddings, Hadwiger's conjecture, Tutte's edge...
A New Proof Of The Independence Ratio Of Triangle-Free Cubic Graphs
Christopher Carl Heckman, Robin Thomas
: Staton proved that every triangle-free graph on n vertices with maximum degree three has an independent set of size at least 5n=14. A simpler proof was found by Jones. We give a yet simpler proof,...