*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.