PDFLINK |

# Legacy of Robin Thomas

Communicated by *Notices* Associate Editor Emilie Purvine

Robin Thomas, a renowned mathematician, passed away on March 26, 2020, following a long struggle against Amyotrophic Lateral Sclerosis (ALS). He was born in Czechoslovakia in 1962 and earned his doctoral degree in 1985 from Charles University. Following the invitation of Neil Robertson and Paul Seymour, Robin arrived in the United States in 1988 and had positions at Ohio State University and Bellcore. He joined Georgia Tech in 1989 as a faculty member and was appointed a Regent’s Professor in 2010. In 2016, he received the Class of 1934 Distinguished Professor Award, the highest honor for a professor at Georgia Tech.

Robin’s research was in combinatorics, especially in structural graph theory, with applications to different branches of mathematics and computer science. He was awarded the Fulkerson Prize twice: in 1994 for the proof of the 5-color case of Hadwiger’s conjecture and in 2009 for the proof of the Strong Perfect Graph Theorem. In 2011, he was awarded the Karel Janeček Foundation Neuron Prize for Lifetime Achievement in Mathematics. He became an inaugural fellow of the American Mathematical Society in 2012 and a fellow of the Society for Industrial and Applied Mathematics in 2018.

In addition to his prominent achievements in research, Robin’s remarkable leadership had a profound influence in education. Robin served as the director of the Algorithms, Combinatorics, and Optimization (ACO) program at Georgia Tech from 2006 to 2019. The ACO program at Georgia Tech, founded around 1991, is an elite interdisciplinary doctoral program that combines three rapidly growing research areas in computer science, mathematics, and industrial engineering. Robin was involved in the founding of the ACO program and was the second director of the program. His long-term service preserved and enhanced the prestigious reputation of the program.

Sadly, in 2008, Robin was diagnosed with ALS which gradually decreased his muscle strength, resulting in difficulty moving, speaking, and breathing. But he never gave up working. He delivered a very encouraging commencement address at Georgia Tech in 2016. He kept doing research, teaching, advising students, and leading the ACO program until a few months prior to his tragic passing in 2020. Indeed, he accomplished this all with truly remarkable diligence and passion.

Robin’s professionalism and personality heavily influenced my life. He offered me constant and supportive encouragement not only verbally but also through his actions since I was a graduate student. It continuously benefits me even today. My conversations with him were always inspiring, and his suggestions were always comprehensive and considerate. He is a role model not only in academia but also in my daily life. It is my good fortune to have had Robin as my advisor.

In this article, I will briefly survey some of Robin’s research achievements among his more than 100 papers, focusing on his most important work and results joint with his students and postdocs. My goal is to give a rough picture of Robin’s contribution and the trajectory of his research while simultaneously highlighting the far reaches of his mentoring. I will finish the article by briefly remarking on Robin’s leadership for the ACO program.

Before we survey Robin’s research we define some common concepts and notation from graph theory that will be used throughout. A *graph* consists of a set (called the *set of vertices*) and a set (called the *set of edges*), where every element of is a subset of with size 2 and we say are *adjacent* and is *incident* with and We assume that graphs are finite (i.e., . and are finite) in this article, unless otherwise specified. As our goal is to give a picture of Robin’s research instead of providing precise mathematical statements, sometimes for simplicity we will allow to be a multi-set without explicitly stating this. The *complete graph* on vertices, denoted by is the graph consisting of , pairwise adjacent vertices. We use to denote a *complete multi-partite graph*, which is a graph whose set of vertices can be partitioned into parts with size , …, , respectively, such that any two vertices in different parts are adjacent. ,

## 1. Well-quasi-ordering and Infinite Graphs

Robin’s work in the early stages of his career was mainly on well-quasi-ordering theory and infinite graphs.

A *quasi-ordering* on a set is a reflexive and transitive binary relation on A quasi-ordering . on is a *well-quasi-ordering* if for every infinite sequence , … over , there exist , such that Well-quasi-ordering is important in mathematics, logic, and computer science. One particular strength of well-quasi-ordering is that every property that is closed under a well-quasi-ordering .Footnote^{1} can be characterized by finitely many objects. For example, the celebrated Graph Minor Theorem of Robertson and Seymour states that the minor relation is a well-quasi-ordering on graphs and implies that every graph property that is closed under vertex-deletion, edge-deletion, and edge-contraction (such as the property that being able to be drawn in a fixed surface without edge-crossing) can be characterized by a finite set of graphs and can be tested in polynomial time. (See Figure 4 for an illustration for edge-contraction.)

^{1}

That is, there exists a well-quasi-ordering such that an element satisfies this property implies that every element with satisfies this property.

The study of well-quasi-ordering can be traced back to the 1940s to two conjectures of Vazsonyi on graphs: trees and subcubic graphs are well-quasi-ordered by the topological minor relation, respectively. Here we say that a graph is a *topological minor* of another graph if some subgraph of is isomorphic to a graph that can be obtained from by repeatedly subdividing edges. (See Figure 5 for an illustration for subdivisions.) Both conjectures have been solved. The tree conjecture is now known as the Kruskal Tree Theorem and is important in reverse mathematics, an area in logic that seeks to determine the axioms that are required to prove theorems. However, the topological minor relation is not a well-quasi-ordering on all graphs. For example, the set consisting of the graphs obtained from cycles by doubling all their edges is an infinite antichain with respect to the topological minor relation.

Since Vazsonyi’s conjectures cannot be generalized to all graphs, two natural directions can be considered: one is to characterize all graphs that can be well-quasi-ordered by the topological minor relation, and the other is to consider weaker graph containment relations and try to generalize them to infinite graphs if possible. Robin’s work spans both directions.

We start with the second direction. The topological minor relation is closely related to the minor relation, as shown by Kuratowski’s theorem on characterizing planar graphs: a graph can be drawn in the plane with no edge-crossing if and only if and are not topological minors of and if and only if and are not minors of Here we say that a graph . is a *minor* of another graph if is isomorphic to a graph that can be obtained from a subgraph of by repeatedly contracting edges. If contains as a topological minor, then contains as a minor, but not vice versa. Hence the minor relation is a natural candidate for considering well-quasi-ordering. Robertson and Seymour proved that the minor relation is a well-quasi-ordering on (finite) graphs, confirming a conjecture of Wagner, in their seminal series of around 20 papers. This result is now known as the Graph Minor Theorem. The next natural question is whether the minor relation is a well-quasi-ordering on infinite graphs as well. Robin 18 disproved it by constructing infinitely many uncountable graphs that form an antichain with respect to the minor relation. The case for countable infinite graphs remains open. On the other hand, Robin 19 proved that for any planar graph the minor relation is a well-quasi-ordering on the set of , free finite or infinite graphs. -minor

One strategy to prove that a quasi-ordering on a set is a well-quasi-ordering is the following. If this relation is not a well-quasi-ordering, then there exists an infinite sequence , … over , such that is not smaller than with respect to this relation for all In particular, . is not smaller than any other entry of the sequence. So it gives an extra property for all entries other than and reduces the well-quasi-ordering problem on to the one on a subset of consisting of objects with lower complexity. This addresses the importance of studying the structure of free finite or infinite graphs, for any fixed graph -minor Such a theorem for finite graphs is the cornerstone of Robertson and Seymour’s proof of their Graph Minor Theorem. Joint with Robertson and Seymour, Robin .13 provided an exact characterization of free graphs in terms of their structures, for any fixed infinite cardinal -minor .

The case for finite cardinals is more complicated, and no exact characterization is known. Robertson and Seymour proved that for every integer every , free finite graph admits a certain well-described structure, and -minor does not admit this structure for some larger integer Though it is not an exact characterization for . free graphs, it is sufficient to prove the Graph Minor Theorem and a number of results in graph theory and computer science. In joint work with Diestel, Robin extended Robertson and Seymour’s result by showing that every -minor free infinite graph admits the same structure, for any fixed integer -minor .

Now we move back to topological minors of graphs. Recall that there is an infinite antichain with respect to the topological minor relation. Among any known such infinite antichain, one can find a minor for arbitrarily large integers -topological in graphs in this antichain, where is the graph obtained from a path of length by doubling all edges. Robertson in the late 1980s conjectured that this is the only obstruction: for any fixed integer (finite) graphs with no , minor are well-quasi-ordered by the topological minor relation. Robin and I proved this conjecture and characterized all topological minor-closed classes of graphs that are well-quasi-ordered by the topological minor relation. As in the proof of the Graph Minor Theorem, we -topological8 proved a structure theorem for minor free graphs for any fixed graph -topological on the way to proving Robertson’s conjecture.

For finite graphs, problems about topological minors are usually more complicated and behave less nicely than the ones about minors. For example, it is more complicated to state the aforementioned structural theorem for minor free graphs than Robertson and Seymour’s theorem for -topological free graphs. However, the situation seems different for infinite graphs. For example, Robin, joint with Robertson and Seymour, proved that for any infinite cardinal -minor an infinite graph is , minor free if and only if it admits a well-founded tree-decomposition of width -topological .

Another interesting result of Robin is a construction of Lebesgue non-measurable sets in by using the simple fact that finite or infinite graphs with no odd cycles are bipartite.

## 2. Graph Minors

We have seen that Robin made significant contributions on graph minors in the previous section. But those are just the tip of the iceberg. In this section, we will focus on Robin’s contributions to (finite) graph minors.

Before Robertson and Seymour were able to prove the Graph Minor Theorem, they considered the fundamental question of finding a structural description of free graphs, for any fixed graph -minor The simplest non-trivial case is when . is a tree. Robertson and Seymour proved that for every tree (or forest) there exists an integer , such that every free graph can be represented by a collection -minor of closed intervals in such that each vertex corresponds to an interval in every point in , is contained in at most intervals in and if two vertices are adjacent, then the corresponding two intervals overlap. As graphs are finite, we may assume that those intervals in , are finite and have integral endpoints. So those intervals can be treated as subpaths of a fixed path. Such a representation of a graph by using a collection subpaths of a host path (or intervals in is called a )*path-decomposition* of The .*path-width* of a graph is the minimum such that no vertex of the host path is contained in more than paths in the collection. Hence the aforementioned result can be equivalently stated as the following: for every tree (or forest) there exists an integer , such that every free graph has path-width at most -minor Since there exists no constant . such that every tree has path-width at most the above result is a rough characterization for graphs that forbid a tree (or forest) as a minor. But the value of , obtained by Robertson and Seymour is not optimal. In joint work with Bienstock, Robertson, and Seymour, Robin improved the constant to be which is optimal. In joint work with Dang, Robin further proved that every 2-connected graph with large path-width contains a large apex-forest or a large outerplanar graph as a minor, answering a question of Seymour. The same result was independently proved by Huynh, Joret, Micek, and Wood. ,

A *tree-decomposition* of a graph is defined in a way that is similar to a path-decomposition: it consists of a collection of subtrees of a fixed tree such that each subtree corresponds to a vertex of and the subtrees corresponding to any two adjacent vertices of , intersect. The *tree-width* of is the minimum such that has a tree-decomposition such that no vertex in the host tree is contained in more than subtrees in the collection. It is known that forests are exactly the graphs with tree-width at most 1, though trees can have arbitrarily large path-width. Moreover, a tree-decomposition of tells how to construct in a tree-like fashion. For every vertex of the host tree we call the subgraph of , induced by the vertices corresponding to the subtrees of in the tree-decomposition containing the *bag* corresponding to Then . can be constructed by repeatedly gluing bags in the same way as we construct the host tree by repeatedly attaching vertices.

Tree-width is an important notion in graph theory and computer science. For example, Courcelle proved that for any fixed any property definable in monadic second-order logic can be tested for graphs with tree-width at most , in linear time. But the running time heavily depends on the tree-width.

What can we say about the graphs with large tree-width? It is known that planar graphs can have arbitrarily large tree-width. Robertson and Seymour proved that planar graphs are the only obstructions for having small tree-width: for every planar graph there exists an integer , such that every free graph has tree-width at most -minor Recall that the running time of Courcelle’s algorithm heavily depends on the tree-width. Hence reducing . to be as small as possible is crucial. The constant in Robertson and Seymour’s theorem is enormous; Robin together with Robertson and Seymour improved to be which was further improved to be polynomial in , by Chekuri and Chuzhoy around 20 years later.

How about if we forbid a general graph as a minor? Robertson and Seymour proved that for every graph every , free graph admits a tree-decomposition whose bags are “nearly embeddable” in a surface in which -minor cannot be embedded. It is a very deep and difficult result and is a cornerstone of the proof of the Graph Minor Theorem. Recently, joint with Kawarabayashi and Wollan, Robin provided a simpler proof.

We have discussed the structure of graphs with no fixed large graph as a minor. Those results are very general and sufficient for numerous applications. However, they are asymptotic results in the sense that they only show that every free graph satisfies a property that is not satisfied by another graph that is similar to -minor This is likely to be unavoidable because . is very general.

Can we get a more precise structural description for graphs with no fixed small graph as a minor? Somethings about these are known: free graphs are exactly forests; -minor free graphs are exactly the graphs of tree-width at most 2; -minor free graphs are exactly the graphs that admit a tree-decomposition, each bag of which is a planar graph or a special graph on 8 vertices sharing at most 3 vertices with each of the other bags. However, there is evidence showing that the structure of -minor free graphs is much more complicated. Restricting the problems to highly connected graphs might simplify the situation. For example, the aforementioned result for -minor implies that a 4-connected graph is free if and only if it is planar. Along this line, Jørgensen conjectured that every 6-connected -minor free graph is an apex-graph. An -minor*apex-graph* is a graph such that is planar for some vertex Apex-graphs are . free since planar graphs are -minor free. So Jørgensen’s conjecture is equivalent to saying that a 6-connected graph is -minor free if and only if it is an apex-graph. Though Jørgensen’s conjecture remains open, Robin together with Kawarabayashi, Norine, and Wollan proved that it is true for all large graphs. -minor

This theorem was further strengthened by Norine and Robin by replacing by any constant and replacing by a constant only depending on .

free graphs are closely related to two natural ways of extending the notion of planar embedding. We say that a graph is -minor*linkless embeddable* if it can be embedded in such that any two disjoint cycles have zero linking number; a graph is *flat embeddable* if it can be embedded in such that every cycle is the boundary of an open disk in disjoint from the graph. Planar graphs are obviously linkless embeddable and flat embeddable, but is not linkless or flat embeddable. More non-linkless embeddable graphs can be constructed by - and - operations.

The - operation deletes the 3 edges of a and adds a new vertex adjacent to the 3 vertices of this -subgraph the -subgraph; - operation deletes a vertex of degree 3 and adds 3 edges between the 3 neighbors of the deleted vertex. (See Figure 6.) All graphs that can be obtained from by repeatedly applying - and - operations are not linkless or flat embeddable. There are 7 such graphs, where one of them is the Petersen graph (see Figure 7). The class of these 7 graphs is called the *Petersen family*. Joint with Robertson and Seymour, Robin proved the following theorem that connects these three notions, where the equivalence between Statements 1 and 3 was conjectured by Sachs, and the equivalence between Statements 1 and 2 was conjectured by Böhme and Saran.

Another significant result of Robin about excluded minor theory is the following separator theorem proved in joint work with Alon and Seymour.

The above separator theorem generalizes the famed separator theorem of Lipton and Tarjan on planar graphs and is useful for designing efficient divide-and-conquer algorithms for numerous problems. For example, it leads to subexponential time algorithms of some NP-hard problems for minor-closed families and a algorithm for solving a system of -time linear equations with variables whose sparsity structure corresponds to a graph in a minor-closed family.

Now we turn our attention to Robin’s work on algorithms related to graph minors. Recall that Courcelle proved that every property expressible by monadic second-order logic can be tested in linear time on bounded tree-width graphs. This result cannot be extended to general minor-closed families, unless NP=P. For example, testing whether a planar graph is 3-colorable or not is an NP-hard problem, but 3-colorability is expressible by monadic second-order logic. Hence in an attempt to enlarge the class of input graphs, one has to restrict the set of properties to be tested. Such natural candidates are the first-order properties. In joint with Dvořák and Král’, Robin successfully proved that first-order properties can be tested in linear time on any class of graphs of bounded expansion. This is a class of graphs that cannot be made arbitrarily dense by contracting disjoint subgraphs with bounded radius and is a far-reaching generalization of minor-closed families.

Now we move to the extremal aspect. Euler’s formula implies that every planar graph on vertices has at most edges. What is the maximum number of edges a free graph can have? Planar graphs are -minor free, so every graph that can be made planar by deleting at most -minor vertices is free, and such a graph has at most -minor edges. Mader showed that the bound provided by this simple observation gives the optimal answer for It is no longer true for . since and graphs that can be obtained from copies of by identifying cliques of size 5 are counterexamples; Jørgensen showed that they are exactly the only counterexamples. In joint work with Song, Robin further characterized the case. They 17 proved that every free graph on -minor vertices with at least edges is either isomorphic to or can be obtained from copies of by identifying cliques of size 6. Such Mader-type results are useful for attacking Hadwiger’s conjecture. (See Section 3 for more details about Hadwiger’s conjecture.) But if they were true for all sufficiently large then they would imply that the average degree of , free graphs is -minor which is far from the correct average degree , as shown by Kostochka and independently by Thomason. However, Seymour and Robin conjectured that the Mader-type theorem holds for large highly connected graphs: for every there exists an integer , such that every -connected free graphs on -minor vertices has at most edges. This was proved by Norin and Robin.

## 3. Graph Coloring

Arguably one of the most famous problems in graph theory is the Four Color Problem, which asks whether every planar graph is 4-colorable (i.e., the vertices can be colored with 4 colors so that any two adjacent vertices receive different colors), raised by Guthrie in 1852. Even though this question looks elementary, it is equivalent to numerous statements in different branches of mathematics and is surprisingly difficult to prove. Robin made significant contributions on graph coloring, mainly related to the Four Color Problem and its variants.

A proof of the Four Color Problem was published by Appel and Haken in the 1970s. Even though this proof represents a major breakthrough, it was not fully accepted for two reasons: one is that part of the proof uses a computer and cannot be checked by hand, and the other is that the part of the proof that is supposed to be checked by hand is extremely complicated and tedious. Robertson, Sanders, Seymour, and Robin tried to read this proof, but very soon gave up. They decided to make their own proof, and they did it 12 in the 1990s. Though their proof still relies on a computer, it is significantly simpler and has been independently verified (including the computer part) by different groups of people. Due to this work, now it is safe to call it the Four Color Theorem.

In 1943, Hadwiger conjectured that for any every , free graph is -minor Since planar graphs are -colorable. free, Hadwiger’s conjecture is a far-reaching generalization of the Four Color Theorem. Hadwiger’s conjecture is not hard to prove for -minor Wagner used his structural theorem for ; free graphs mentioned in the previous section to prove that the case -minor is equivalent to the Four Color Theorem. Joint with Robertson and Seymour, Robin proved the next case by proving that the case is also equivalent to the Four Color Theorem. For this work, Robin was awarded his first Fulkerson Prize. Hadwiger’s conjecture remains open for .

The *chromatic number* of a graph is the minimum such that is The -colorable.*clique number* of is the maximum size of a set of pairwise adjacent vertices in Clearly, the chromatic number is at least the clique number. One natural question is whether these two numbers are equal. In other words, is every . free graph -subgraph for any -colorable, It is well-known that the answer is negative. So Hadwiger’s conjecture can be viewed as an attempt to remedy this by forbidding ? as a more general structure. But can we characterize all graphs whose chromatic number equals the clique number? Since the disjoint union of and an arbitrary graph whose chromatic number is smaller than satisfies that the chromatic number equals the clique number, any meaningful characterization must consider all induced subgraphs. This leads to the notion of perfect graphs.

A graph is *perfect* if every induced subgraph of satisfies that its chromatic number equals its clique number. Typical examples of non-perfect graphs include any odd cycle of length at least 5 and its complement. Berge proposed two conjectures in 1961. The first one, proved by Lovász in 1972, states that every graph is perfect if and only if its complement is perfect, and it is called the Perfect Graph Theorem. The second conjecture implies the first one and states that the aforementioned odd cycles of length at least 5 and their complements are exactly the obstructions to being perfect. Joint with Chudnovsky, Robertson and Seymour, Robin proved the second conjecture, which is now known as the Strong Perfect Graph Theorem, and for this, Robin was awarded his second Fulkerson Prize.

The Four Color Theorem is equivalent to the statement that every 2-edge-connected 3-regular planar graph is 3-edge-colorable (i.e., the edges can be colored with 3 colors so that any two edges sharing an end receive different colors). In 1966, Tutte conjectured that every 2-edge-connected 3-regular graph with no Petersen minor is 3-edge-colorable. Since the Petersen graph is non-planar, Tutte’s conjecture is stronger than the Four Color Theorem. Tutte’s conjecture was solved by a series of papers of Robin and his collaborators. There are two natural kinds of graphs having no Petersen minor: apex graphs and double-cross graphs, where a graph is a *double-cross graph* if it can be drawn in the plane with at most two crossings, and each crossing is on the infinite region. Joint with Robertson and Seymour, Robin showed that every minimum counterexample to Tutte’s conjecture is either an apex graph or a double-cross graph. Joint with Sanders, Robin proved that every 2-edge-connected 3-regular apex graph is 3-edge-colorable. Joint with Edwards, Sanders, and Seymour, Robin proved that every 2-edge-connected 3-regular double-cross graph is 3-edge-colorable. Hence Tutte’s conjecture follows.

The Four Color Theorem is optimal in the sense that 4 colors are necessary for some planar graphs, such as A classical result of Grötzsch states that 3 colors are enough if triangles are forbidden. Even though Grötzsch’s theorem ensures the existence of a 3-coloring, it was unclear how to find such a coloring efficiently. Robin, together with Dvořák and Kawarabayashi, gave a linear time algorithm to find a 3-coloring for a given triangle-free planar graph. On the other hand, Grötzsch’s theorem is no longer true for graphs embedded in surfaces other than the plane. But Robin, together with Dvořák and Král’, gave a linear time algorithm to test whether a given triangle-free graph embedded in a fixed surface is 3-colorable or not, and a quadratic time algorithm to find a 3-coloring if such a coloring exists. .

Besides the aforementioned variation of Grötzsch’s theorem about surfaces of higher Euler genus, a potential strengthening of Grötzsch’s theorem was proposed by Havel: forbidding triangles that are close to each other suffices. It was proved in Robin’s joint work with Dvořák and Král’.

The condition of having no triangles can be restated in terms of the *girth*, which is the length of the shortest cycle of a graph. So a statement equivalent to Grötzsch’s theorem says that every planar graph with girth at least 4 is 3-colorable. It reduces the number of necessary colors from the case with girth 3. So it is natural to expect that one can get even nicer coloring results for the case with girth at least 5. One such result was proved by Robin, together with Walls, showing that every graph with girth at least 5 embeddable in the Klein bottle is 3-colorable. This result answers a question of Woodburn and complements results of Thomassen who proved the same for the projective plane and torus. Postle and I later proved a result about the edge-density for 4-critical graphs, giving a unified proof of the aforementioned three results.

Raising the girth not only enables us to strengthen Grötzsch’s theorem to surfaces with higher Euler genus but also enables us to strengthen the “colorability.” A *list-assignment* of a graph is a function that maps each vertex to a set of colors; a graph is if we can assign each vertex -colorable a color in such that any pair of adjacent vertices receive different colors; a list-assignment is a * -list-assignment* if it maps each vertex to a set of size at least A graph is .* -choosable* if it is for any -colorable -list-assignment Every . graph is -choosable since a -colorable is an -coloring for some -coloring that maps every vertex to the same set. Thomassen proved that every planar graph with girth at least 5 is 3-choosable and every planar graph is 5-choosable. Thomassen’s results motivated many results and conjectures about coloring graphs embeddable in a surface with girth at least by using colors or Joint with Postle, Robin -list-assignments.10 developed a theory of linear isoperimetric inequalities for graphs on surfaces and applied it to prove a number of new results and known results, such as coloring embedded graphs with no short non-null-homotopic cycles or proving the existence of exponentially many different colorings.

## 4. Graphs on Surfaces

We have discussed many of Robin’s results about coloring graphs embeddable in a surface. In this section, we will discuss his other results for those graphs.

One group of such results is about Hamiltonian cycles. A *Hamiltonian cycle* in a graph is a cycle that contains all vertices of Looking for Hamiltonian cycles is a popular topic in graph theory. It is also related to the Four Color Theorem. Recall that the Four Color Theorem is equivalent to the statement that every 2-edge-connected 3-regular planar graph is 3-edge-colorable. It is easy to see that if a 3-regular planar graph has a Hamiltonian cycle, then it is 3-edge-colorable. Hence one might expect to prove the Four Color Theorem by proving that every 2-edge-connected 3-regular planar graph has a Hamiltonian cycle. However, this expectation is too good to be true. Tutte constructed a 3-connected 3-regular planar graph that has no Hamiltonian cycle, thereby disproving a conjecture of Tait. Tutte also proved that every 4-connected planar graph has a Hamiltonian cycle. .

Two conjectures for extending Tutte’s result to graphs embeddable in surfaces with higher Euler genus were proposed. One of them was conjectured by Grünbaum, stating that every 4-connected graph embeddable in the projective plane has a Hamiltonian cycle. Joint with Yu, Robin 20 proved this conjecture. The other conjecture was proposed by Grünbaum, and independently by Nash-Williams, stating that every 4-connected toroidal graph (i.e., a graph that can be drawn in the torus without edge-crossing) has a Hamiltonian cycle. This conjecture remains open, but Robin proved two weakenings. In another joint paper with Yu, he proved that every 5-connected toroidal graph has a Hamiltonian cycle; in joint work with Yu and Zang, he proved that every 4-connected toroidal graph has a Hamiltonian path.

Another set of Robin’s results is about planar covers and graphs embedded in the projective plane. A *planar cover* of a graph is a planar graph such that there exists a mapping such that for every vertex , gives a bijection between the set of neighbors of in and the set of neighbors of in Planar covers naturally arise from graphs embedded in the projective plane. If . is a graph embedded in the projective plane, then the lifting of this embedding into the universal covering surface of the projective plane gives a planar cover of So if . is embeddable in the projective plane, then has a (finite) planar cover. The converse statement is not true, as the disjoint union of two copies of has a planar cover but cannot be embedded in the projective plane. Negami conjectured that the converse statement holds if only connected graphs are considered: every connected graph has a (finite) planar cover if and only if it is embeddable in the projective plane. Negami’s conjecture remains open. Due to work of Archdeacon, of Fellows and Negami, and of Hliněný, it is known that Negami’s conjecture holds if and only if has no finite planar cover. Even though this conjecture seems almost solved as it only requires checking a property of a small graph, testing this property for does not seem to be a finite problem. On the other hand, if Negami’s conjecture is false, namely if there exist graphs non-embeddable in the projective plane having planar covers, then it is unclear what those graphs look like. A characterization of such graphs can be described by the set such that every connected graph has no finite planar cover if and only if it contains some graph in as a minor. In joint work with Hliněný, Robin 6 gave an explicit description of a finite set and proved that is a subset of .

Planar covers can also be used to construct minor-minimal graphs with even branch-width. Branch-width is a graph parameter that is asymptotically equivalent to tree-width, and sometimes it is more convenient to use. For any fixed integer graphs with branch-width at most , form a minor-closed family. So it is natural to ask what the minor-minimal graphs with fixed branch-width are. A graph embedded in a surface is * -representative* if every homotopically non-trivial closed curve in intersects the embedding at least times. This notion frequently appears in the study of graphs embedded in surfaces. An embedded graph is *minor-minimally -representative* if it has no isolated vertex and is but contracting any edge or deleting any edge makes it -representative,non- Randby proved that every minor-minimally -representative. graph embedded in the projective plane can be obtained from the -representative projective grid by repeatedly taking - and - operations. So they can be constructed explicitly. Joint with Inkmann, Robin provided an explicit construction of minor-minimal graphs with even branch-width by showing that for every integer if , is a graph embedded in the projective plane such that it is minor-minimally then the planar cover of -representative, obtained by lifting is a minor-minimal graph of branch-width .

## 5. Matching Theory and Pfaffian Orientations

Matching theory is one of the most fundamental research directions in graph theory and boosts the development of combinatorial optimization. Robin made significant contributions in this area, especially for those related to Pfaffian orientations.

A *matching* in a graph is a set of edges that do not share ends; a matching in a graph is *perfect* if every vertex of is incident with an edge in Given a bipartite graph . with a bipartition with we can define a 0-1 , matrix such that for any the , of -entry equals 1 if and only if the vertex in -th is adjacent to the vertex in -th So a perfect matching in . corresponds to a permutation matrix whose is at most the -entry of -entry for any , Hence the number of perfect matchings in . is the permanent of Conversely, given a 0-1 square matrix . one can construct a bipartite graph , such that and the permanent of equals the number of the perfect matchings of Hence computing the permanent of a 0-1 matrix is equivalent to computing the number of perfect matchings in a bipartite graph. .

Even though the definitions of permanent and determinant are similar, these two notions have significantly different behaviors. For example, computing the permanent is even when the matrix is a 0-1 matrix, but computing the determinant can be done efficiently. Pólya in 1913 asked what kind of square 0-1 matrix P-complete satisfies the property that there exists a matrix obtained from by changing some of the 1’s to in such a way that the determinant of ’s equals the permanent of If such a matrix . exists, we call it a *Pólya matrix* of Vazirani and Yannakakis proved that a 0-1 square matrix has a Pólya matrix if and only if the corresponding bipartite graph has a Pfaffian orientation. A .*Pfaffian orientation* of a graph is an orientation such that for every central even cycle in traversing , in any direction sees an odd number of edges with consistent direction and an odd number of edges with opposite direction, where a subgraph of is *central* if has a perfect matching. (See Figure 8 for an example.) Hence Pólya’s question is equivalent to characterizing the bipartite graphs that have a Pfaffian orientation.

Little proved that a bipartite graph has a Pfaffian orientation if and only if none of its central subgraph is isomorphic to an even subdivision of Little’s characterization is elegant, but it seems that it is not strong enough to give a polynomial time algorithm for determining whether a bipartite graph has a Pfaffian orientation. Joint with Robertson and Seymour, Robin .15 proved a characterization and gave a polynomial time algorithm to test whether a bipartite graph has a Pfaffian orientation, and hence gave a polynomial time algorithm to test whether a given 0-1 square matrix has a Pólya matrix. The following characterization for braces is the key theorem for their characterization. (A *brace* is a bipartite graph such that any matching of size 2 of is contained in a perfect matching of a graph ; is obtained from graphs and by a *central -sum* if can be obtained from a disjoint union of and by identifying a central induced 4-cycle in with a central induced 4-cycle in and deleting any number of edges in the identified 4-cycle.)

(See Figure 9 for an illustration of the Heawood graphs.)

The importance of braces comes from the work of Edmonds, Lovász, and Pulleybank about tight cut decompositions. They showed that any graph with every edge contained in a perfect matching admits no non-trivial tight cut if and only if it is a brace or a brick. (A *brick* is a 3-connected graph such that deleting any two distinct vertices from it results in a graph that has a perfect matching.) The decision problem about whether a graph has a Pfaffian orientation can also be reduced to the problem on braces and bricks. So the aforementioned characterization for braces admitting a Pfaffian orientation leads to a characterization for bipartite graphs admitting a Pfaffian orientation. Hence, to complete the characterization for graphs admitting a Pfaffian orientation, it suffices to consider bricks. However, no such characterization that can lead to a polynomial time algorithm for testing whether a graph is Pfaffian or not is known. In joint work with Norine, Robin made progress on understanding bricks. In particular, they provided a structure theorem for bricks by showing that every brick can be obtained from a graph in a list of specific graphs by splitting vertices and adding edges in a certain way.

## 6. Directed Graphs

We finish the outline of Robin’s research by mentioning some of his work on directed graphs.

Let be a class of graphs or directed graphs. There are two natural types of problems commonly asked in combinatorial optimization. One of them is a *packing problem*: what is the maximum number of disjoint subgraphs of a graph or directed graph each isomorphic to a member of The other is a ?*covering problem*: what is the minimum number of vertices required to intersect all subgraphs of isomorphic to members of Many problems in graph theory can be modeled as one of them. For example, the maximum size of a matching of a graph ? is when and the minimum size of a ;*vertex-cover* of (another extensively studied notion) is when .

These two problems can be formulated as integer programming problems, and they are dual to each other. Note that as we need at least , vertices to intersect disjoint objects. But unlike linear programming problems, cannot be upper bounded in terms of for general One direction in graph theory is to prove that certain classes . do not have this bad property.

Formally, has the *Erdős-Pósa property* if there exists a function such that for every graph (or directed graph) , Having the Erdős-Pósa property has advantages. For example, if one can efficiently approximate one of . and then the Erdős-Pósa property immediately gives an efficient approximation of the other. For example, it is easy to show that , has the Erdős-Pósa property with So it gives a .factor- approximation for the minimum size of a vertex-cover of a graph by simply finding the maximum size of a matching of which can be done in polynomial time, even though finding the exact value of the minimum size of a vertex-cover is NP-hard. ,

A classical result of Erdős and Pósa states that the set of all cycles has the Erdős-Pósa property. Younger in 1973 conjectured that the set of all directed cycles also has the Erdős-Pósa property, where the special case for directed graphs with no two disjoint directed cycles was independently conjectured by Gallai earlier. Joint with Reed, Robertson, and Seymour, Robin 11 proved this conjecture. We denote the maximum number of disjoint directed cycles in by and we denote the minimum number of vertices in , required to intersect all directed cycles by .

Another interesting question is to characterize all directed graphs with This question probably has no nice answer. We consider the following weakening: find the characterization for the directed graphs . such that for every subgraph of We say that . *packs* if for every subgraph of Note that this notion can be viewed as an analog of perfect graphs, and it is related to minors of directed graphs. .

There are many reasonable ways to define minors of directed graphs. Here we only consider butterfly minors, which is one of the most extensively studied notions for directed graph minors. We say that a directed graph is a *butterfly minor* of another directed graph if can be obtained from a subgraph of by repeatedly contracting an edge that is either the unique out-going edge of its tail or the unique in-going edge of its head. Note that the edge-contractions mentioned in the definition of butterfly minors preserve the strongly connected components. It is also easy to see that every butterfly minor of a directed graph that packs also packs. Hence one can characterize directed graphs that pack by providing the minimal butterfly minor obstructions.

The *doubly directed cycle* of length is the directed graph obtained from the cycle of length by replacing each edge by a pair of directed edges with opposite directions. It is easy to see that the doubly directed cycle of length has at most disjoint directed cycles and requires at least vertices to intersect all directed cycles. So doubly directed cycles of odd length do not pack. Joint with Guenin, Robin 5 proved that doubly directed cycles of odd length and another special directed graph on vertices, called are exactly the minimal butterfly minor obstructions for directed graphs that pack. ,

Note that can be obtained from the Heawood graph by certain operations. Those operations connect the notions of directed graphs and perfect matchings in bipartite graphs. In fact, the proof of Theorem 10 uses the characterization of braces that have a Pfaffian orientation mentioned in the previous section.

## 7. Leadership and Mentorship

Besides Robin’s remarkable mentorship witnessed by prolific work joint with his students and postdocs mentioned in previous sections, we briefly remark on Robin’s long-term leadership for the ACO program.

The Algorithms, Combinatorics, and Optimization (ACO) program at Georgia Tech is the oldest interdisciplinary PhD program at Georgia Tech founded around 1991. It is one of only two programs of their named genre in the United States. (The other ACO program is at Carnegie Mellon University created one or two years earlier than the one at Georgia Tech.) The ACO program highlights three rapidly growing areas of research: analysis of algorithms, combinatorics, and discrete and combinatorial optimization. As we have seen in previous sections, Robin’s work spans all three areas and shows that the boundary line between those areas is vague. Many faculties in different departments of Georgia Tech had worked on related areas since the 1970s, motivating the creation of the ACO program with a unique curriculum design that spans three academic units in Georgia Tech.

In 1993, Robin’s student, Daniel Sanders, became the first graduate of the ACO program. Robin was the second director of the ACO program, serving from 2006 to 2019. When Robin took over the position from the first director, Richard Duke, the ACO program was already well-established in the sense that the concerns about its viability and appeal to applicants with the highest quality had essentially resolved. Robin not only maintained the prestige of the ACO program but also elevated it. By 2011, the ACO program was considered an elite academic program by any of the usual metrics. Today, 30 years after its establishment, the ACO program remains strong and thriving. Robin’s long-term service and extraordinary contributions from other affiliated faculties definitely played important roles. ACO alumni gathered at Georgia Tech in 2017 to celebrate the 25th anniversary of the ACO program and gave public talks. Many of them recalled their days at Georgia Tech and the graph theory course taught by Robin. Indeed, Robin was part of the daily life of an ACO person. We refer readers to 9 for a history of the ACO program.

We close this article by including contributions from some of Robin’s former students and postdocs that highlight his excellent mentoring.

As his PhD student, Robin taught me how to think about research. An excellent researcher, Robin had a wonderful taste in problems. While we both shared a love of graph coloring, particularly the Four Color Theorem and all its extensions and generalizations, Robin was always open to a new problem if it was natural and well-motivated. Robin taught me to never shy away from the hard problems of mathematics but instead to embrace them, to believe that problems worth working on are their own reward.

Robin also taught me the importance of communicating mathematical ideas. Through Robin’s guidance during our many collaborations, I learned how to write mathematics professionally, to understand that technical writing was not about persuasion but precision. I learned that a colleague reading my paper had to be able to reconstruct exactly what I was doing without having me there to walk them through it. For presentations, Robin instilled in me that each slide should carry its own weight. Since I graduated in 2012, I have taken to heart all the lessons I learned from Robin. Robin shaped how I think about mathematics and how I approach research, writing, and presentations. To this day, I still find myself asking what would Robin say?

Robin was the best mentor I ever had. I can honestly say I would not be where I am today as a tenured professor if it were not for Robin; indeed, I wonder sometimes if I would even be in math. Robin literally changed my life but he also changed me. He taught me many things but most of all he taught me by example with his constant courage, perseverance, and enthusiasm in the face of adversity.

Luke Postle is an associate professor at University of Waterloo. His email address is lpostle@uwaterloo.ca.

I first met Robin in 1999, during the symposium on Graph Drawing in Prague where he gave an invited plenary talk on graph planarity and related topics. I still remember his talk today, which was given with crystal clarity whilst covering so many deep results from the theory of graph minors, a rapidly emerging area at that time. In 2001, Robin gave an invited talk at the first workshop of the GROW series and during this workshop, I became engrossed in a detailed discussion with Robin concerning the extension of Erdős-Posa type results on planar graphs (that I had obtained earlier) to surfaces of higher genus. It was extremely impressive how broad and deep Robin’s knowledge was, not only of graph theory, but across the entire field of mathematics. This made me realize the importance of seeing mathematics in its unity and led me to devote a significant amount of time while working on my PhD to learning topics from other areas of mathematics and computer science, even if I did not intend to do any research in those areas. In 2005, I was honored to become Robin’s postdoc and the year that I spent at Georgia Tech really changed the direction of my research career. Of course, I learnt a lot from graph theory while working with Robin but it was his open-minded approach to mathematics, graph theory in particular, and the routine involvement of computers in his work which have served as a huge source of inspiration during my academic career. However, Robin was not only an outstanding researcher but also an excellent teacher as I witnessed during my postdoc stay and frequent subsequent visits to Georgia Tech. He paid extreme attention to the delivery of material in his classes and I am sure he would not mind me sharing a brief story related to this. Once whilst having lunch with Robin, a student that Robin had taught a couple of years earlier came to thank him for conducting the class in such a way that he could build so much upon it in his forthcoming years at Georgia Tech. Certainly in my view, this is one of the greatest accolades a teacher can receive! Robin was, and still is, a source of inspiration for my academic work and, until his untimely passing, I continued to consult him for scientific advice on various matters. I stay very much indebted to Robin for the amount I learnt from him, his overall support and a great deal of inspiration, all of which are impossible to comprehend in words.

Dan Král’ is a Donald Ervin Knuth Professor at Masaryk University and a honorary professor at University of Warwick. His email address is dkral@fi.muni.cz.

## Acknowledgment

The author thanks Sigrun Andradottir, Luke Postle, and Petr Hliněný for some suggestions when preparing this article.

## References

- [1]
- Noga Alon, Paul Seymour, and Robin Thomas,
*A separator theorem for nonplanar graphs*, J. Amer. Math. Soc.**3**(1990), no. 4, 801–808, DOI 10.2307/1990903. MR1065053Show rawAMSref`\bib{separator}{article}{ author={Alon, Noga}, author={Seymour, Paul}, author={Thomas, Robin}, title={A separator theorem for nonplanar graphs}, journal={J. Amer. Math. Soc.}, volume={3}, date={1990}, number={4}, pages={801--808}, issn={0894-0347}, review={\MR {1065053}}, doi={10.2307/1990903}, }`

Close amsref.^{✖} - [2]
- Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas,
*The strong perfect graph theorem*, Ann. of Math. (2)**164**(2006), no. 1, 51–229, DOI 10.4007/annals.2006.164.51. MR2233847Show rawAMSref`\bib{perfect}{article}{ author={Chudnovsky, Maria}, author={Robertson, Neil}, author={Seymour, Paul}, author={Thomas, Robin}, title={The strong perfect graph theorem}, journal={Ann. of Math. (2)}, volume={164}, date={2006}, number={1}, pages={51--229}, issn={0003-486X}, review={\MR {2233847}}, doi={10.4007/annals.2006.164.51}, }`

Close amsref.^{✖} - [3]
- Zdeněk Dvořák, Daniel Král’, and Robin Thomas,
*Testing first-order properties for subclasses of sparse graphs*, J. ACM**60**(2013), no. 5, Art. 36, 24, DOI 10.1145/2499483. MR3124685Show rawAMSref`\bib{alg_fo}{article}{ author={Dvo\v {r}\'{a}k, Zden\v {e}k}, author={Kr\'{a}l', Daniel}, author={Thomas, Robin}, title={Testing first-order properties for subclasses of sparse graphs}, journal={J. ACM}, volume={60}, date={2013}, number={5}, pages={Art. 36, 24}, issn={0004-5411}, review={\MR {3124685}}, doi={10.1145/2499483}, }`

Close amsref.^{✖} - [4]
- Zdeněk Dvořák, Daniel Kráľ, and Robin Thomas,
*Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies*, J. Combin. Theory Ser. B**150**(2021), 244–269, DOI 10.1016/j.jctb.2020.04.006. MR4280261Show rawAMSref`\bib{close_triangle}{article}{ author={Dvo\v {r}\'{a}k, Zden\v {e}k}, author={Kr\'{a}\v {l}, Daniel}, author={Thomas, Robin}, title={Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies}, journal={J. Combin. Theory Ser. B}, volume={150}, date={2021}, pages={244--269}, issn={0095-8956}, review={\MR {4280261}}, doi={10.1016/j.jctb.2020.04.006}, }`

Close amsref.^{✖} - [5]
- Bertrand Guenin and Robin Thomas,
*Packing directed circuits exactly*, Combinatorica**31**(2011), no. 4, 397–421, DOI 10.1007/s00493-011-1687-5. MR2861237Show rawAMSref`\bib{pack_di_cycle}{article}{ author={Guenin, Bertrand}, author={Thomas, Robin}, title={Packing directed circuits exactly}, journal={Combinatorica}, volume={31}, date={2011}, number={4}, pages={397--421}, issn={0209-9683}, review={\MR {2861237}}, doi={10.1007/s00493-011-1687-5}, }`

Close amsref.^{✖} - [6]
- Petr Hliněný and Robin Thomas,
*On possible counterexamples to Negami’s planar cover conjecture*, J. Graph Theory**46**(2004), no. 3, 183–206, DOI 10.1002/jgt.10177. MR2063369Show rawAMSref`\bib{negami_conj}{article}{ author={Hlin\v {e}n\'{y}, Petr}, author={Thomas, Robin}, title={On possible counterexamples to Negami's planar cover conjecture}, journal={J. Graph Theory}, volume={46}, date={2004}, number={3}, pages={183--206}, issn={0364-9024}, review={\MR {2063369}}, doi={10.1002/jgt.10177}, }`

Close amsref.^{✖} - [7]
- Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, and Paul Wollan,
*minors in large 6-connected graphs*, J. Combin. Theory Ser. B**129**(2018), 158–203, DOI 10.1016/j.jctb.2017.09.007. MR3758245Show rawAMSref`\bib{large_jorgensen}{article}{ author={Kawarabayashi, Ken-ichi}, author={Norine, Serguei}, author={Thomas, Robin}, author={Wollan, Paul}, title={$K_6$ minors in large 6-connected graphs}, journal={J. Combin. Theory Ser. B}, volume={129}, date={2018}, pages={158--203}, issn={0095-8956}, review={\MR {3758245}}, doi={10.1016/j.jctb.2017.09.007}, }`

Close amsref.^{✖} - [8]
- Chun-Hung Liu and Robin Thomas,
*Excluding subdivisions of bounded degree graphs*, J. Combin. Theory Ser. B**134**(2019), 1–35, DOI 10.1016/j.jctb.2018.05.001. MR3906628Show rawAMSref`\bib{excluding_topo}{article}{ author={Liu, Chun-Hung}, author={Thomas, Robin}, title={Excluding subdivisions of bounded degree graphs}, journal={J. Combin. Theory Ser. B}, volume={134}, date={2019}, pages={1--35}, issn={0095-8956}, review={\MR {3906628}}, doi={10.1016/j.jctb.2018.05.001}, }`

Close amsref.^{✖} - [9]
- R. Gary Parker,
*The ACO program at Georgia Tech*, https://aco.gatech.edu/sites/default/files/images/aco_history.pdf, (2018). - [10]
- Luke Postle and Robin Thomas,
*Hyperbolic families and coloring graphs on surfaces*, Trans. Amer. Math. Soc. Ser. B**5**(2018), 167–221, DOI 10.1090/btran/26. MR3882883Show rawAMSref`\bib{hyperbolic}{article}{ author={Postle, Luke}, author={Thomas, Robin}, title={Hyperbolic families and coloring graphs on surfaces}, journal={Trans. Amer. Math. Soc. Ser. B}, volume={5}, date={2018}, pages={167--221}, review={\MR {3882883}}, doi={10.1090/btran/26}, }`

Close amsref.^{✖} - [11]
- Bruce Reed, Neil Robertson, Paul Seymour, and Robin Thomas,
*Packing directed circuits*, Combinatorica**16**(1996), no. 4, 535–554, DOI 10.1007/BF01271272. MR1433641Show rawAMSref`\bib{younger_conj}{article}{ author={Reed, Bruce}, author={Robertson, Neil}, author={Seymour, Paul}, author={Thomas, Robin}, title={Packing directed circuits}, journal={Combinatorica}, volume={16}, date={1996}, number={4}, pages={535--554}, issn={0209-9683}, review={\MR {1433641}}, doi={10.1007/BF01271272}, }`

Close amsref.^{✖} - [12]
- Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas,
*The four-colour theorem*, J. Combin. Theory Ser. B**70**(1997), no. 1, 2–44, DOI 10.1006/jctb.1997.1750. MR1441258Show rawAMSref`\bib{4ct}{article}{ author={Robertson, Neil}, author={Sanders, Daniel}, author={Seymour, Paul}, author={Thomas, Robin}, title={The four-colour theorem}, journal={J. Combin. Theory Ser. B}, volume={70}, date={1997}, number={1}, pages={2--44}, issn={0095-8956}, review={\MR {1441258}}, doi={10.1006/jctb.1997.1750}, }`

Close amsref.^{✖} - [13]
- Neil Robertson, Paul Seymour, and Robin Thomas,
*Excluding infinite clique minors*, Mem. Amer. Math. Soc.**118**(1995), no. 566, vi+103, DOI 10.1090/memo/0566. MR1303095Show rawAMSref`\bib{inf_clique_minor}{article}{ author={Robertson, Neil}, author={Seymour, Paul}, author={Thomas, Robin}, title={Excluding infinite clique minors}, journal={Mem. Amer. Math. Soc.}, volume={118}, date={1995}, number={566}, pages={vi+103}, issn={0065-9266}, review={\MR {1303095}}, doi={10.1090/memo/0566}, }`

Close amsref.^{✖} - [14]
- Neil Robertson, Paul Seymour, and Robin Thomas,
*Hadwiger’s conjecture for graphs -free*, Combinatorica**13**(1993), no. 3, 279–361, DOI 10.1007/BF01202354. MR1238823Show rawAMSref`\bib{had_k6}{article}{ author={Robertson, Neil}, author={Seymour, Paul}, author={Thomas, Robin}, title={Hadwiger's conjecture for $K_6$-free graphs}, journal={Combinatorica}, volume={13}, date={1993}, number={3}, pages={279--361}, issn={0209-9683}, review={\MR {1238823}}, doi={10.1007/BF01202354}, }`

Close amsref.^{✖} - [15]
- Neil Robertson, P. D. Seymour, and Robin Thomas,
*Permanents, Pfaffian orientations, and even directed circuits*, Ann. of Math. (2)**150**(1999), no. 3, 929–975, DOI 10.2307/121059. MR1740989Show rawAMSref`\bib{Pfaffian}{article}{ author={Robertson, Neil}, author={Seymour, P. D.}, author={Thomas, Robin}, title={Permanents, Pfaffian orientations, and even directed circuits}, journal={Ann. of Math. (2)}, volume={150}, date={1999}, number={3}, pages={929--975}, issn={0003-486X}, review={\MR {1740989}}, doi={10.2307/121059}, }`

Close amsref.^{✖} - [16]
- Neil Robertson, Paul Seymour, and Robin Thomas,
*Sachs’ linkless embedding conjecture*, J. Combin. Theory Ser. B**64**(1995), no. 2, 185–227, DOI 10.1006/jctb.1995.1032. MR1339849Show rawAMSref`\bib{linkless_embed}{article}{ author={Robertson, Neil}, author={Seymour, Paul}, author={Thomas, Robin}, title={Sachs' linkless embedding conjecture}, journal={J. Combin. Theory Ser. B}, volume={64}, date={1995}, number={2}, pages={185--227}, issn={0095-8956}, review={\MR {1339849}}, doi={10.1006/jctb.1995.1032}, }`

Close amsref.^{✖} - [17]
- Zi-Xia Song and Robin Thomas,
*The extremal function for minors*, J. Combin. Theory Ser. B**96**(2006), no. 2, 240–252, DOI 10.1016/j.jctb.2005.07.008. MR2208353Show rawAMSref`\bib{extre_k9}{article}{ author={Song, Zi-Xia}, author={Thomas, Robin}, title={The extremal function for $K_9$ minors}, journal={J. Combin. Theory Ser. B}, volume={96}, date={2006}, number={2}, pages={240--252}, issn={0095-8956}, review={\MR {2208353}}, doi={10.1016/j.jctb.2005.07.008}, }`

Close amsref.^{✖} - [18]
- Robin Thomas,
*A counterexample to “Wagner’s conjecture” for infinite graphs*, Math. Proc. Cambridge Philos. Soc.**103**(1988), no. 1, 55–57, DOI 10.1017/S0305004100064616. MR913450Show rawAMSref`\bib{counter_wqo_uncount}{article}{ author={Thomas, Robin}, title={A counterexample to ``Wagner's conjecture'' for infinite graphs}, journal={Math. Proc. Cambridge Philos. Soc.}, volume={103}, date={1988}, number={1}, pages={55--57}, issn={0305-0041}, review={\MR {913450}}, doi={10.1017/S0305004100064616}, }`

Close amsref.^{✖} - [19]
- Robin Thomas,
*Well-quasi-ordering infinite graphs with forbidden finite planar minor*, Trans. Amer. Math. Soc.**312**(1989), no. 1, 279–313, DOI 10.2307/2001217. MR932450Show rawAMSref`\bib{wqo_bdd_tw_inf}{article}{ author={Thomas, Robin}, title={Well-quasi-ordering infinite graphs with forbidden finite planar minor}, journal={Trans. Amer. Math. Soc.}, volume={312}, date={1989}, number={1}, pages={279--313}, issn={0002-9947}, review={\MR {932450}}, doi={10.2307/2001217}, }`

Close amsref.^{✖} - [20]
- Robin Thomas and Xingxing Yu,
*projective-planar graphs are Hamiltonian -connected*, J. Combin. Theory Ser. B**62**(1994), no. 1, 114–132, DOI 10.1006/jctb.1994.1058. MR1290634Show rawAMSref`\bib{ty}{article}{ author={Thomas, Robin}, author={Yu, Xingxing}, title={$4$-connected projective-planar graphs are Hamiltonian}, journal={J. Combin. Theory Ser. B}, volume={62}, date={1994}, number={1}, pages={114--132}, issn={0095-8956}, review={\MR {1290634}}, doi={10.1006/jctb.1994.1058}, }`

Close amsref.^{✖}

## Credits

Figure 1 is courtesy of Jan Kratochvil.

Figure 2 is courtesy of Sigrun Andradottir.

Figure 3 is courtesy of Sheridan Moore.

Figures 4–9 are courtesy of Chun-Hung Liu.

Photo of Chun-Hung Liu is courtesy of Jiajin Yu.