Topics in Graph Theory 2  GRT

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.

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.