Instructor: Dr. Gábor SIMONYI
Text: R. Diestel, Graph Theory + handouts GTB
Prerequisite: Some degree of mathematical maturity is needed for this faster 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 a current
area: information theoretic graph theory.
Topics:
Basics: Graphs, degrees, paths and cycles,
independent sets, cliques, isomorphism, subgraphs, complement of a graph,
trees, Euler tours, other
notions of graphs.
Hamilton cycles: sufficient conditions for Hamiltonicity, theorems of Dirac, Ore, Pósa, and Chvátal, the optimality of Chvátal's theorem.
Coloring: The concept of chromatic number, its relation to the clique
number, Mycielsky's construction, bipartite graphs, list coloring,
choice number, its relation to the chromatic
number, list coloring conjecture, Galvin's theorem.
Coloring edges and matchings: Vizing's theorem, matchings in bipartite
graphs, Kőnig--Hall--Frobenius theorem, theorems of Gallai,
Tutte's theorem.
Planarity: Euler's lemma, Kuratowski's theorem, coloring of planar graphs, list coloring of planar graphs.
Perfect graphs: Basic examples, perfectness of comparability graphs, the perfect graph theorem, properties of minimally imperfect graphs and the strong perfect graph theorem.
Outlook on algorithmic questions: Examples of good characterization, minimax theorems, basic complexity classes.
Capacities of graphs: Products of graphs, Shannon capacity, Sperner
capacity, capacity of graph families, connections with extremal set
theory, Gargano-Körner-Vaccaro theorem,
application to Rényi's qualitative independence problem.
Entropy of graphs: The entropy function, its combinatorial and
intuitive meaning, vertex packing polytope, definition and basic
properties of
graph entropy, applications,
additivity properties, a characterization of perfect graphs.