George Neil Robertson (born November 30, 1938) is a mathematician working mainly in

topological graph theory In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in ...

, currently a distinguished professor emeritus at the

Ohio State University The Ohio State University, commonly called Ohio State or OSU, is a public land-grant research university in Columbus, Ohio. A member of the University System of Ohio, it has been ranked by major institutional rankings among the best publ ...

Education

Robertson earned his B.Sc. from Brandon College in 1959, and his Ph.D. in 1969 at the

University of Waterloo The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario, Canada. The main campus is on of land adjacent to "Uptown" Waterloo and Waterloo Park. The university also operates ...

under his

doctoral advisor A doctoral advisor (also dissertation director, dissertation advisor; or doctoral supervisor) is a member of a university faculty whose role is to guide graduate students who are candidates for a doctorate, helping them select coursework, as well ...

William Tutte.

Biography

In 1969, Robertson joined the faculty of the Ohio State University, where he was promoted to Associate Professor in 1972 and Professor in 1984. He was a consultant with Bell Communications Research from 1984 to 1996. He has held visiting faculty positions in many institutions, most extensively at Princeton University from 1996 to 2001, and at Victoria University of Wellington, New Zealand, in 2002. He also holds an adjunct position at

King Abdulaziz University King Abdulaziz University (KAU) ( ar, جامعة الملك عبد العزيز) is a public university in Jeddah, Saudi Arabia. With over 117,096 students in 2022, it is the largest university in the country. Located in south Jeddah, the univ ...

Saudi Arabia Saudi Arabia, officially the Kingdom of Saudi Arabia (KSA), is a country in Western Asia. It covers the bulk of the Arabian Peninsula, and has a land area of about , making it the fifth-largest country in Asia, the second-largest in the A ...

Research

Robertson is known for his work in

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, and particularly for a long series of papers co-authored with Paul Seymour and published over a span of many years, in which they proved the

Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is c ...

(formerly Wagner's Conjecture). This states that families of graphs closed under the

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

operation may be characterized by a

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. T ...

forbidden minor In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...

s. As part of this work, Robertson and Seymour also proved the

graph structure theorem In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seven ...

describing the graphs in these families. Additional major results in Robertson's research include the following: *In 1964, Robertson discovered the

Robertson graph In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4- regular undirected graph with 19 vertices and 38 edges named after Neil Robertson. The Robertson graph is the unique (4,5)-cage graph and was discovered by Rob ...

, the smallest possible 4-

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...

with girth five. *In 1994, with Seymour and

Robin Thomas Robin may refer to: Animals * Australasian robins, red-breasted songbirds of the family Petroicidae * Many members of the subfamily Saxicolinae (Old World chats), including: **European robin (''Erithacus rubecula'') **Bush-robin ** Forest r ...

, Robertson extended the number of colors for which the Hadwiger conjecture relating graph coloring to graph minors is known to be true. As of 2012 this remains the strongest known result on this conjecture. *In 1996, Robertson, Seymour, Thomas, and Daniel P. Sanders published a new proof of the four color theorem, confirming the Appel–Haken proof which until then had been disputed. Their proof also leads to an efficient

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

for finding 4-colorings of planar graphs. *In 2006, Robertson, Seymour, Thomas, and

Maria Chudnovsky Maria Chudnovsky (born January 6, 1977) is an Israeli-American mathematician working on graph theory and combinatorial optimization. She is a 2012 MacArthur Fellow. Education and career Chudnovsky is a professor in the department of mathematic ...

, proved the long-conjectured strong perfect graph theorem characterizing the

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfe ...

s by forbidden

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

Awards and honors

Robertson has won the

Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...

three times, in 1994 for his work on the Hadwiger conjecture, in 2006 for the Robertson–Seymour theorem, and in 2009 for his proof of the strong perfect graph theorem. He also won the Pólya Prize (SIAM) in 2004, the OSU Distinguished Scholar Award in 1997, and the Waterloo Alumni Achievement Medal in 2002. In 2012 he became a fellow of the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

.List of Fellows of the American Mathematical Society
retrieved 2013-07-07.

References

External links

Neil Robertson's homepage
at

Short conference video
Neil Robertson - ''Some thoughts on Hadwiger's Conjecture''. June 28, 1999. Video produced by

Bojan Mohar Bojan Mohar (born September 21, 1956) is a Slovenian and Canadian mathematician, working in graph theory. He is a professor of mathematics at the University of Ljubljana and the holder of a Canada Research Chair in graph theory at Simon Fraser Unive ...