#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

A graph consists of a set of elements together with a binary relation defined on the set. Graphs can be represented by diagrams in which the elements are shown as points and the binary relation as lines joining pairs of points. It is this representation which gives graph theory its name and much of its appeal. However, the true importance of graphs is that, as basic mathematical structures, they arise in diverse contexts, both theoretical and applied. The concept of a graph was known already to Euler in the early eighteenth century, but it was the notorious Four-Colour Problem, posed by F. Guthrie in the mid-nineteenth century, that spurred the development of this simple concept into a flourishing theory. In this century, interactions between graph theory and linear algebra, probability theory, number theory, group theory, geometry, topology, and other branches of mathematics have led to further developments in the subject. In recent years, its fundamental links with operations research and computer science have resulted in the fast growth and greatly increased prominence of graph theory.

Graph theory has played a major role in the research activities of the Department since its inception in 1967, due primarily to the influence and example of W.T. Tutte, a leading figure in the subject for several decades. Current areas of research include algebraic graph theory (association schemes, knot polynomials, eigenvalues), algorithmic graph theory, asymptotic enumeration of graphs, extremal graph theory, matching theory, minimax theorems, and Ramsey theory.

- Jane Gao: Random graph theory
- Jim Geelen: Graph minors
- Chris Godsil: Algebraic graph theory
- Bertrand Guenin: Signed graphs
- Penny Haxell: Extremal combinatorics, graph theory
- Peter Nelson: Extremal combinatorics
- Luke Postle: Graph colouring, topological and structural graph theory
- Bruce Richter: Graph theory & Topology of Surfaces
- Sophie Spirkl: Induced subgraphs, structural graph theory

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.