Graph Theory(D)
GRAPH THEORY (D)
No specific prerequisites.
Introduction
- Basic definitions. Trees and spanning trees. Bipartite graphs. Euler circuits. Elementary properties of planar graphs. Statement of Kuratowski’s theorem. [3]
Connectivity and matchings
- Matchings in bipartite graphs; Hall’s theorem and its variants. Connectivity and Menger’s theorem. [3]
Extremal graph theory
- Long paths, long cycles and Hamilton cycles. Complete subgraphs and Tur´an’s theorem. Bipartite subgraphs and the problem of Zarankiewicz. The Erd˝os-Stone theorem; *sketch of proof*. [5]
Eigenvalue methods
- The adjacency matrix and the Laplacian. Strongly regular graphs. [2]
Graph colouring
- Vertex and edge colourings; simple bounds. The chromatic polynomial. The theorems of Brooks and Vizing. Equivalent forms of the four colour theorem; the five colour theorem. Heawood’s theorem for surfaces; the torus and the Klein bottle. [5]
Ramsey theory
- Ramsey’s theorem (finite and infinite forms). Upper bounds for Ramsey numbers. [3]
Probabilistic methods
- Basic notions; lower bounds for Ramsey numbers. The model G(n,p); graphs of large girth and large chromatic number. The clique number. [3]
Appropriate books
- † B.Bollob´as Modern Graph Theory. Springer 1998
- R.Diestel Graph Theory. Springer 2000
- D.West Introduction to Graph Theory. Prentice Hall 1999
Associated GitHub Page
https://jaircambridge.github.io/Graph-Theory-D/