﻿ BSM

## Graph Theory — GRT

• Instructor: Casey Tompkins and Nika Salia
• Contact: ctompkins496 at gmail.com/nikasalia at yahoo.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.