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. |
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. |
|
|