Course description: The course begins with an overview of the fundamental concepts of graph theory, followed by an in-depth discussion of some classical topics as well as some aspects of a current area: information theoretic graph theory.

Topics covered (tentative):

• Basics: Graphs, directed graphs, degrees, paths and cycles, independent sets, cliques, isomorphism, subgraphs, complement of a graph, trees, Euler tours, line graphs.
• Hamilton cycles: Necessary and sufficient conditions for Hamiltonicity, theorems of Dirac, Ore, Pósa, and Chvátal.
• Matchings: Matchings in bipartite graphs, Hall’s theorem and König’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, Four Color Theorem, list coloring of planar graphs.
• Ramsey theory: Basic graph Ramsey theorem, theorems of Chvátal, Nešetřil and Rödl.
• Perfect graphs: Basic examples, 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, local chromatic number and its relation to the chromatic number.
• 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.