Graph Theory, Track B — GRT.B

Instructor:  Dr. Gábor Simonyi
Text: R. Diestel, Graph Theory + handouts
Prerequisites: Some degree of mathematical maturity is needed for this relatively fast paced course. No prior knowledge of graph theory is required.

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:
Basics: Graphs, degrees, paths and cycles, independent sets, cliques, isomorphism, sub- graphs, complement of a graph, trees, Euler tours.
Hamilton cycles: sufficient conditions for Hamiltonicity, theorems of Dirac, Ore, Posa, and Chvatal, the optimality of Chvatal’s theorem.
Matchings: matchings in bipartite graphs, Hall’s theorem and K ?onig’s theorem, Tutte’s theorem, stable matchings, Gale-Shapley theorem.
Colorings: The concept of chromatic number, its relation to the clique number, Mycielsky’s construction, coloring edges, Vizing’s theorem, list coloring, choice number, its relation to the chromatic number, list coloring conjecture, Galvin’s theorem.
Planarity: Euler’s formula, Kuratowski’s theorem, coloring of planar graphs, list coloring of planar graphs.
Basics of extremal graph theory: Tur ´an’s theorem and related results, graph Ramsey theorems.
Perfect graphs: Basic examples, perfectness of comparability graphs, the Perfect Graph Theorem, the Strong Perfect Graph Theorem.
More advanced topics on colorings: Fractional chromatic number, the chromatic number of Kneser graphs and Schrijver graphs.
Capacities of graphs: Products of graphs, Shannon capacity and its bounds, connection to Ramsey numbers, Sperner capacity and other related concepts originated in information theory.