Instructor: Dr. Miklós RUSZINKÓ
Text: class notes
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.