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 Brandon University is a university located in the city of Brandon, Manitoba, Canada, with an enrollment of 3375 (2020) full-time and part-time undergraduate and graduate students. The current location was founded on July 13, 1899, as Brandon C ...

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 Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...

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 William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...

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 conne ...

, 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 cl ...

(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. Th ...

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 forbidden ...

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 Robe ...

, 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 outdegree o ...

with

girth Girth may refer to: ;Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * 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 ro ...

, Robertson extended the number of colors for which the

Hadwiger conjecture There are several conjectures known as the Hadwiger conjecture or Hadwiger's conjecture. They include: * Hadwiger conjecture (graph theory), a relationship between the number of colors needed by a given graph and the size of its largest clique mino ...

relating

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

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 Daniel P. Sanders is an American mathematician. He is known for his 1996 efficient proof (algorithm) of proving the Four color theorem (with Neil Robertson, Paul Seymour, and Robin Thomas). He used to be a guest professor of the department of com ...

published a new proof of the

four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sh ...

, 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 Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

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 perfec ...

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) Pólya Prize may refer to: *George Pólya Prize, awarded by the Society for Industrial and Applied Mathematics (SIAM) *Pólya Prize (LMS), awarded by the London Mathematical Society See also * George Pólya Award The George Pólya Award is pres ...

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 ...

. {{DEFAULTSORT:Robertson, Neil 20th-century American mathematicians 21st-century American mathematicians Graph theorists University of Waterloo alumni Living people 1938 births Fellows of the American Mathematical Society Ohio State University faculty