Topics in Graph Theory  GTA

Instructor:  Dr. Ervin GYŐRI

Text: B. Bollobás, Modern Graph Theory

Prerequisite: Some basics of discrete mathematics is needed for this 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, focusing on extremal graph theory questions

Basics: Graphs, degrees, components, paths and cycles, independent sets, cliques, isomorphism, subgraphs, complement of a graph, trees, Euler tours, spanning trees, cycle structure of graphs, Erdős-Gallai theorem on paths

Hamilton cycles: Sufficient conditions for Hamiltonicity, theorems of Dirac, Ore, Pósa, etc., 2-factors

Coloring: The concept of chromatic number, its relation to the clique number, theorems on chromatic number.

Coloring edges and matchings: Vizing's theorem, matchings in bipartite graphs, Konig--Hall--Frobenius theorem, Tutte's theorem.

Network flows and connectivity: Networks, Ford-Fulkerson theorem, connectivity numbers, Menger's theorems, k-connected and k-linked graphs, graph minors in dense graphs.

Planarity: Euler's lemma, Kuratowski's theorem, coloring of planar graphs.

Extremal graph theory: Turán's theorem and related results, the role of the chromatic number in extremal graph theory, graph Ramsey theorems, Szemeredi's regularity lemma and its applications, Erdős-Stone theorem, extremal graphs not containing cycles of given length and other particular graphs. Use of probabilistic and linear algebraic methods