Legacy of Robin Thomas

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.

Figure 1.

Robin Thomas.

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.

Figure 2.

Robin’s family.

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.

Figure 3.

Robin’s academic family. The photo was taken at the banquet during the conference at Georgia Tech in 2012 celebrating Robin’s work and his 50th birthday.

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 $G$ consists of a set $V(G)$ (called the set of vertices) and a set $E(G)$ (called the set of edges), where every element $e$ of $E(G)$ is a subset $\{u,v\}$ of $V(G)$ with size 2 and we say $u,v$ are adjacent and $e$ is incident with $u$ and $v$. We assume that graphs are finite (i.e., $V(G)$ and $E(G)$ 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 $E(G)$ to be a multi-set without explicitly stating this. The complete graph on $t$ vertices, denoted by $K_t$, is the graph consisting of $t$ pairwise adjacent vertices. We use $K_{t_1,t_2,\dots ,t_k}$ to denote a complete multi-partite graph, which is a graph whose set of vertices can be partitioned into $k$ parts with size $t_1$, $t_2$, …, $t_k$, 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 $X$ is a reflexive and transitive binary relation on $X$. A quasi-ordering $\preceq$ on $X$ is a well-quasi-ordering if for every infinite sequence $a_1$, $a_2$, … over $X$, there exist $i<j$ such that $a_i \preceq a_j$. 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⁠¹ 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.)

¹

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

✖

Figure 4.

Edge-contraction. The graph at the right-hand-side is a minor of the graph at the left-hand-side. But the former is not a topological minor of the latter.

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 $H$ is a topological minor of another graph $G$ if some subgraph of $G$ is isomorphic to a graph that can be obtained from $H$ 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.

Figure 5.

Subdividing an edge. The graph on the left-handside is a topological minor of the graph on the right-hand-side. The former is also a minor of the latter since the former can be obtained from the latter by contracting an edge.

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 $G$ can be drawn in the plane with no edge-crossing if and only if $K_5$ and $K_{3,3}$ are not topological minors of $G$ and if and only if $K_5$ and $K_{3,3}$ are not minors of $G$. Here we say that a graph $H$ is a minor of another graph $G$ if $H$ is isomorphic to a graph that can be obtained from a subgraph of $G$ by repeatedly contracting edges. If $G$ contains $H$ as a topological minor, then $G$ contains $H$ 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 $H$, the minor relation is a well-quasi-ordering on the set of $H$-minor free finite or infinite graphs.

One strategy to prove that a quasi-ordering on a set $X$ is a well-quasi-ordering is the following. If this relation is not a well-quasi-ordering, then there exists an infinite sequence $a_1$, $a_2$, … over $X$ such that $a_i$ is not smaller than $a_j$ with respect to this relation for all $i<j$. In particular, $a_1$ is not smaller than any other entry of the sequence. So it gives an extra property for all entries other than $a_1$ and reduces the well-quasi-ordering problem on $X$ to the one on a subset of $X$ consisting of objects with lower complexity. This addresses the importance of studying the structure of $H$-minor free finite or infinite graphs, for any fixed graph $H$. 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 $K_\kappa$-minor free graphs in terms of their structures, for any fixed infinite cardinal $\kappa$.

The case for finite cardinals $\kappa$ is more complicated, and no exact characterization is known. Robertson and Seymour proved that for every integer $k$, every $K_k$-minor free finite graph admits a certain well-described structure, and $K_{k'}$ does not admit this structure for some larger integer $k'$. Though it is not an exact characterization for $K_k$-minor 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 $K_k$-minor free infinite graph admits the same structure, for any fixed integer $k$.

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 $R_k$-topological minor for arbitrarily large integers $k$ in graphs in this antichain, where $R_k$ is the graph obtained from a path of length $k$ by doubling all edges. Robertson in the late 1980s conjectured that this is the only obstruction: for any fixed integer $k$, (finite) graphs with no $R_k$-topological 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 8 proved a structure theorem for $H$-topological minor free graphs for any fixed graph $H$ 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 $H$-topological minor free graphs than Robertson and Seymour’s theorem for $H$-minor free graphs. However, the situation seems different for infinite graphs. For example, Robin, joint with Robertson and Seymour, proved that for any infinite cardinal $\kappa$, an infinite graph is $K_{\kappa }$-topological minor free if and only if it admits a well-founded tree-decomposition of width $<\kappa$.

Another interesting result of Robin is a construction of Lebesgue non-measurable sets in ${\mathbb{R}}$ 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 $H$-minor free graphs, for any fixed graph $H$. The simplest non-trivial case is when $H$ is a tree. Robertson and Seymour proved that for every tree (or forest) $H$, there exists an integer $f_H$ such that every $H$-minor free graph can be represented by a collection $S$ of closed intervals in ${\mathbb{R}}$ such that each vertex corresponds to an interval in $S$, every point in ${\mathbb{R}}$ is contained in at most $f_H+1$ intervals in $S$, and if two vertices are adjacent, then the corresponding two intervals overlap. As graphs are finite, we may assume that those intervals in $S$ are finite and have integral endpoints. So those intervals can be treated as subpaths of a fixed path. Such a representation of a graph $G$ by using a collection subpaths of a host path (or intervals in ${\mathbb{R}}$) is called a path-decomposition of $G$. The path-width of a graph $G$ is the minimum $k$ such that no vertex of the host path is contained in more than $k+1$ paths in the collection. Hence the aforementioned result can be equivalently stated as the following: for every tree (or forest) $H$, there exists an integer $f_H$ such that every $H$-minor free graph has path-width at most $f_H$. Since there exists no constant $c$ such that every tree has path-width at most $c$, the above result is a rough characterization for graphs that forbid a tree (or forest) as a minor. But the value of $f_H$ obtained by Robertson and Seymour is not optimal. In joint work with Bienstock, Robertson, and Seymour, Robin improved the constant $f_H$ to be $\lvert V(H) \rvert -2$, 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 $G$ is defined in a way that is similar to a path-decomposition: it consists of a collection of subtrees of a fixed tree $T$ such that each subtree corresponds to a vertex of $G$, and the subtrees corresponding to any two adjacent vertices of $G$ intersect. The tree-width of $G$ is the minimum $k$ such that $G$ has a tree-decomposition such that no vertex in the host tree $T$ is contained in more than $k+1$ 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 $G$ tells how to construct $G$ in a tree-like fashion. For every vertex $v$ of the host tree $T$, we call the subgraph of $G$ induced by the vertices corresponding to the subtrees of $T$ in the tree-decomposition containing $v$ the bag corresponding to $v$. Then $G$ 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 $k$, any property definable in monadic second-order logic can be tested for graphs with tree-width at most $k$ 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 $H$, there exists an integer $p_H$ such that every $H$-minor free graph has tree-width at most $p_H$. Recall that the running time of Courcelle’s algorithm heavily depends on the tree-width. Hence reducing $p_H$ to be as small as possible is crucial. The constant $p_H$ in Robertson and Seymour’s theorem is enormous; Robin together with Robertson and Seymour improved $p_H$ to be $2^{\mathrm{poly}(\lvert V(H) \rvert +\lvert E(H) \rvert )}$, which was further improved to be polynomial in $\lvert V(H) \rvert +\lvert E(H) \rvert$ by Chekuri and Chuzhoy around 20 years later.

How about if we forbid a general graph $H$ as a minor? Robertson and Seymour proved that for every graph $H$, every $H$-minor free graph admits a tree-decomposition whose bags are “nearly embeddable” in a surface in which $H$ 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 $H$ 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 $H$-minor free graph satisfies a property that is not satisfied by another graph that is similar to $H$. This is likely to be unavoidable because $H$ is very general.

Can we get a more precise structural description for graphs with no fixed small graph $H$ as a minor? Somethings about these are known: $K_3$-minor free graphs are exactly forests; $K_4$-minor free graphs are exactly the graphs of tree-width at most 2; $K_5$-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 $K_6$-minor free graphs is much more complicated. Restricting the problems to highly connected graphs might simplify the situation. For example, the aforementioned result for $K_5$ implies that a 4-connected graph is $K_5$-minor free if and only if it is planar. Along this line, Jørgensen conjectured that every 6-connected $K_6$-minor free graph is an apex-graph. An apex-graph is a graph $G$ such that $G-v$ is planar for some vertex $v$. Apex-graphs are $K_6$-minor free since planar graphs are $K_5$-minor free. So Jørgensen’s conjecture is equivalent to saying that a 6-connected graph is $K_6$-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.

Theorem 1 (7).

There exists an integer $C$ such that every 6-connected $K_6$-minor free graph on at least $C$ vertices is an apex-graph.

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

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

Figure 6.

An example of the $Y$-$\Delta$ operation and the $\Delta$-$Y$ operation.

The $\Delta$-$Y$ operation deletes the 3 edges of a $K_3$-subgraph and adds a new vertex adjacent to the 3 vertices of this $K_3$-subgraph; the $Y$-$\Delta$ 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 $K_6$ by repeatedly applying $\Delta$-$Y$ and $Y$-$\Delta$ 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.

Figure 7.

The Petersen graph.

Theorem 2 (16).

The following are equivalent.

(1)

A graph is linkless embeddable.

(2)

A graph is flat embeddable.

(3)

A graph does not contain any graph in the Petersen family as a minor.

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

Theorem 3 (1).

Let $h$ be an integer, and let $G$ be a $K_h$-minor free graph on $n$ vertices. If $w$ maps each vertex to a nonnegative real number, then there exists $X \subseteq V(G)$ with $\lvert X \rvert \leq h^{3/2}n^{1/2}$ such that $\sum _{v \in V(C)}w(v) \leq \frac{1}{2}\sum _{v \in V(G)}w(v)$ for every component $C$ of $G-X$.

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 $O(n^{3/2})$-time algorithm for solving a system of $n$ linear equations with $n$ 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.

Theorem 4 (3).

Let ${\mathcal{F}}$ be a class of graphs of bounded expansion, and let $\Pi$ be a first-order property of graphs. Then there exists a linear time algorithm that decides whether a graph in ${\mathcal{F}}$ satisfies $\Pi$.

Now we move to the extremal aspect. Euler’s formula implies that every planar graph on $n$ vertices has at most $3n-6$ edges. What is the maximum number of edges a $K_p$-minor free graph can have? Planar graphs are $K_5$-minor free, so every graph that can be made planar by deleting at most $p-5$ vertices is $K_p$-minor free, and such a graph has at most $(p-2)n-{p-1 \choose 2}$ edges. Mader showed that the bound provided by this simple observation gives the optimal answer for $1 \leq p \leq 7$. It is no longer true for $p=8$ since $K_{2,2,2,2,2}$ and graphs that can be obtained from copies of $K_{2,2,2,2,2}$ 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 $p=9$ case. They 17 proved that every $K_9$-minor free graph on $n \geq 9$ vertices with at least $7n-27$ edges is either isomorphic to $K_{2,2,2,3,3}$ or can be obtained from copies of $K_{1,2,2,2,2,2}$ 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 $p$, then they would imply that the average degree of $K_p$-minor free graphs is $O(p)$, which is far from the correct average degree $\Theta (p\sqrt {\log p})$ 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 $p \geq 1$, there exists an integer $N$ such that every $(p-2)$-connected $K_p$-minor free graphs on $n \geq N$ vertices has at most $(p-2)n-{p-1 \choose 2}$ 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 $t \geq 1$, every $K_{t+1}$-minor free graph is $t$-colorable. Since planar graphs are $K_5$-minor free, Hadwiger’s conjecture is a far-reaching generalization of the Four Color Theorem. Hadwiger’s conjecture is not hard to prove for $t \leq 3$; Wagner used his structural theorem for $K_5$-minor free graphs mentioned in the previous section to prove that the case $t=4$ is equivalent to the Four Color Theorem. Joint with Robertson and Seymour, Robin proved the next case by proving that the case $t=5$ is also equivalent to the Four Color Theorem. For this work, Robin was awarded his first Fulkerson Prize. Hadwiger’s conjecture remains open for $t \geq 6$.

Theorem 5 (14).

Every $K_6$-minor free graph is 5-colorable.

The chromatic number of a graph $G$ is the minimum $k$ such that $G$ is $k$-colorable. The clique number of $G$ is the maximum size of a set of pairwise adjacent vertices in $G$. 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 $K_{t+1}$-subgraph free graph $t$-colorable, for any $t$? It is well-known that the answer is negative. So Hadwiger’s conjecture can be viewed as an attempt to remedy this by forbidding $K_{t+1}$ as a more general structure. But can we characterize all graphs whose chromatic number equals the clique number? Since the disjoint union of $K_t$ and an arbitrary graph whose chromatic number is smaller than $t$ 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 $G$ is perfect if every induced subgraph of $G$ 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.

Theorem 6 (2).

A graph is perfect if and only if it does not contain any odd cycle of length at least 5 or its complement as an induced subgraph.

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 $K_4$. 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’.

Theorem 7 (4).

There exists a constant $d$ such that every planar graph with no two triangles within distance at most $d$ is 3-colorable.

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 $L$ that maps each vertex to a set of colors; a graph is $L$-colorable if we can assign each vertex $v$ a color in $L(v)$ such that any pair of adjacent vertices receive different colors; a list-assignment is a $k$-list-assignment if it maps each vertex to a set of size at least $k$. A graph is $k$-choosable if it is $L$-colorable for any $k$-list-assignment $L$. Every $k$-choosable graph is $k$-colorable since a $k$-coloring is an $L$-coloring for some $L$ 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 $3 \leq \ell \leq 5$ by using $8-\ell$ colors or $(8-\ell )$-list-assignments. Joint with Postle, Robin 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 $G$ is a cycle that contains all vertices of $G$. 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 $G$ is a planar graph $L$ such that there exists a mapping $f: V(L) \rightarrow V(G)$ such that for every vertex $v$, $f$ gives a bijection between the set of neighbors of $v$ in $L$ and the set of neighbors of $f(v)$ in $G$. Planar covers naturally arise from graphs embedded in the projective plane. If $G$ 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 $G$. So if $G$ is embeddable in the projective plane, then $G$ has a (finite) planar cover. The converse statement is not true, as the disjoint union of two copies of $K_5$ 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 $K_{1,2,2,2}$ 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 $K_{1,2,2,2}$ 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 $S$ such that every connected graph has no finite planar cover if and only if it contains some graph in $S$ as a minor. In joint work with Hliněný, Robin 6 gave an explicit description of a finite set $T$ and proved that $S$ is a subset of $T$.

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 $w$, graphs with branch-width at most $w$ 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 $\Sigma$ is $k$-representative if every homotopically non-trivial closed curve in $\Sigma$ intersects the embedding at least $k$ times. This notion frequently appears in the study of graphs embedded in surfaces. An embedded graph is minor-minimally $k$-representative if it has no isolated vertex and is $k$-representative, but contracting any edge or deleting any edge makes it non-$k$-representative. Randby proved that every minor-minimally $k$-representative graph embedded in the projective plane can be obtained from the $k \times k$ projective grid by repeatedly taking $\Delta$-$Y$ and $Y$-$\Delta$ 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 $k$, if $G$ is a graph embedded in the projective plane such that it is minor-minimally $k$-representative, then the planar cover of $G$ obtained by lifting is a minor-minimal graph of branch-width $2k$.

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 $M$ in a graph $G$ is perfect if every vertex of $G$ is incident with an edge in $M$. Given a bipartite graph $G$ with a bipartition $(X,Y)$ with $\lvert X \rvert =\lvert Y \rvert =n$, we can define a 0-1 $n \times n$ matrix $A(G)$ such that for any $1 \leq i, j \leq n$, the $(i,j)$-entry of $A(G)$ equals 1 if and only if the $i$-th vertex in $X$ is adjacent to the $j$-th vertex in $Y$. So a perfect matching in $G$ corresponds to a permutation matrix whose $(i,j)$-entry is at most the $(i,j)$-entry of $A(G)$, for any $i,j$. Hence the number of perfect matchings in $G$ is the permanent of $A(G)$. Conversely, given a 0-1 square matrix $W$, one can construct a bipartite graph $H$ such that $W=A(H)$ and the permanent of $W$ equals the number of the perfect matchings of $H$. 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 $\#$P-complete 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 $A$ satisfies the property that there exists a matrix $B$ obtained from $A$ by changing some of the 1’s to $-1$’s in such a way that the determinant of $B$ equals the permanent of $A$. If such a matrix $B$ exists, we call it a Pólya matrix of $A$. 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 $G$ is an orientation such that for every central even cycle $C$ in $G$, traversing $C$ in any direction sees an odd number of edges with consistent direction and an odd number of edges with opposite direction, where a subgraph $H$ of $G$ is central if $G-V(H)$ 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.

Figure 8.

A Pfaffian orientation of the cube.

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 $K_{3,3}$. 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 $G$ such that any matching of size 2 of $G$ is contained in a perfect matching of $G$; a graph $G_0$ is obtained from graphs $G_1$ and $G_2$ by a central $C_4$-sum if $G_0$ can be obtained from a disjoint union of $G_1$ and $G_2$ by identifying a central induced 4-cycle in $G_1$ with a central induced 4-cycle in $G_2$ and deleting any number of edges in the identified 4-cycle.)

Theorem 8 (15).

A brace has a Pfaffian orientation if and only if either it is isomorphic to the Heawood graph, or it can be obtained from planar braces by repeatedly applying the central $C_4$-sum.

Figure 9.

The Heawood graph.

(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 ${\mathcal{F}}$ 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 $\nu _{{\mathcal{F}}}(G)$ of disjoint subgraphs of a graph or directed graph $G$ each isomorphic to a member of ${\mathcal{F}}$? The other is a covering problem: what is the minimum number $\tau _{{\mathcal{F}}}(G)$ of vertices required to intersect all subgraphs of $G$ isomorphic to members of ${\mathcal{F}}$? Many problems in graph theory can be modeled as one of them. For example, the maximum size of a matching of a graph $G$ is $\nu _{{\mathcal{F}}}(G)$ when ${\mathcal{F}}=\{K_2\}$; and the minimum size of a vertex-cover of $G$ (another extensively studied notion) is $\tau _{{\mathcal{F}}}(G)$ when ${\mathcal{F}}=\{K_2\}$.

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

Formally, ${\mathcal{F}}$ has the Erdős-Pósa property if there exists a function $f$ such that for every graph (or directed graph) $G$, $\tau _{{\mathcal{F}}}(G) \leq f(\nu _{{\mathcal{F}}}(G))$. Having the Erdős-Pósa property has advantages. For example, if one can efficiently approximate one of $\nu _{{\mathcal{F}}}(G)$ and $\tau _{{\mathcal{F}}}(G)$, then the Erdős-Pósa property immediately gives an efficient approximation of the other. For example, it is easy to show that $\{K_2\}$ has the Erdős-Pósa property with $f(x)=2x$. So it gives a factor-$2$ approximation for the minimum size of a vertex-cover of a graph $G$ by simply finding the maximum size of a matching of $G$, 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 $D$ by $\nu (D)$, and we denote the minimum number of vertices in $D$ required to intersect all directed cycles by $\tau (D)$.

Theorem 9 (11).

There exists a function $f$ such that $\tau (D) \leq f(\nu (D))$ for every directed graph $D$.

Another interesting question is to characterize all directed graphs $D$ with $\tau (D)=\nu (D)$. This question probably has no nice answer. We consider the following weakening: find the characterization for the directed graphs $D$ such that $\tau (D')=\nu (D')$ for every subgraph $D'$ of $D$. We say that $D$ packs if $\tau (D')=\nu (D')$ for every subgraph $D'$ of $D$. 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 $H$ is a butterfly minor of another directed graph $G$ if $H$ can be obtained from a subgraph of $G$ 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 $k$ is the directed graph obtained from the cycle of length $k$ 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 $k$ has at most $\lfloor k/2 \rfloor$ disjoint directed cycles and requires at least $\lceil k/2 \rceil$ 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 $7$ vertices, called $F_7$, are exactly the minimal butterfly minor obstructions for directed graphs that pack.

Theorem 10 (5).

A directed graph packs if and only if it does not contain any doubly directed cycle of odd length or $F_7$ as a butterfly minor.

Note that $F_7$ 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.

Luke Postle

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.

Dan Král’

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.