Graph Theory

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/