Instructor:  Dr. Miklós RUSZINKÓ

Text: B. Bollobás, Modern Graph Theory

Prerequisite: Some degree of mathematical maturity 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
 

Topics:
Basics: Graphs, degrees, components, paths and cycles, independent sets, cliques, isomorphism, subgraphs, complement of a graph, trees, Euler tours,  other notions of graphs.

Hamilton cycles: The Bondy-Chvatal closure of a graph, sufficient conditions for Hamiltonicity, theorems of Dirac, Ore.

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, Kõnig--Hall--Frobenius theorem, theorems of Gallai,
Tutte's theorem.

Network flows and connectivity: Networks, Ford-Fulkerson theorem, connectivity numbers, Menger's theorems.

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

Turán- and Ramsey-type questions: Turán's theorem and related results, the role of the chromatic number in extremal graph theory,
graph Ramsey theorems.

Probabilistic approach: Some important results showing the power of the probabilistic method in graph theory will be discussed.
 

NOTE: in case of a high demand for the graph theory course another similar course could be introduce, with a slightly different syllabus.