Graph Theory — GRT

  • Instructor: Casey Tompkins
  • Contact: ctompkins496 at gmail.com
  • Prerequisites: Some degree of mathematical maturity is needed for this relatively fast paced course. No prior knowledge of graph theory is required.
  • Text:R. Diestel, Graph Theory (available as a digital edition, too) + handouts

Course description: A brief overview of the basic concepts of graph theory will be followed by an in-depth discussion of some classical chapters of graph theory as well as some aspects of a current area: information theoretic graph theory.

Topics covered:

Topic

Contents

Basics

Graphs, paths and cycles, independent sets, cliques, trees, spanning trees, cycle structure of graphs, Euler tours.

Hamilton cycles

Sufficient conditions for Hamiltonicity, theorems of Dirac, Ore, Pósa, Chvátal.
Hamilton cycles containing given edges.

Matchings

Hall's theorem, König theorem, Tutte's theorem, stable matchings, Gale-Shapley theorem.

Colorings

Chromatic number, its relation to the clique number, Zykov’s and Mycielski’s constructions, coloring edges, Vizing’s theorem, list coloring, chromatic number of the plane.

Planarity

Planar and plane graphs, Kuratowski’s theorem, Euler’s formula, 5-color theorem, Thomassen’s theorem on list coloring of planar graphs, graph minors.

Extremal graph theory

Turán's theorem, Erdős-Stone-Simonovits theorem, Erdős-Gallai theorem, Erdős-Sós conjecture, extremal graphs not containing cycles of a given length, saturation, Erdős-Hajnal-Moon theorem.

Network flows and connectivity

Networks, Ford-Fulkerson theorem, vertex and edge connectivity, Menger's theorems, Mader’s theorem.