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