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
Topics:
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