*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