Graph Theory

Lecturer:

Jan Kratochvíl (gar.)

Tutor:

Jan Kratochvíl (gar.)

Supervisor:

Department of Computer Science

Synopsis:

Attention will be paid both to structural issues and to questions of algorithmization and computational complexity of basic optimization problems restricted to special graph classes, aiming at determining the boundary between polynomially solvable and NP-hard variants of the problems.

Requirements:

General knowledge of discrete mathematics and efficient algorithms.

Syllabus of lectures:

1. Special graph classes and algorithms on them. For many graph classes, most generally hard (NP-hard) problems are solvable in polynomial time. We will explore interval graphs, chordal graphs, perfect graphs, and other graph classes motivated by geometrical applications.

2. Tree decompositions. Many optimization problems solvable in polynomial time for trees are also efficiently solvable for graphs whose structure is close to trees (tree-width, path-width, clique-width). General methods of computation on graphs of bounded widths will be presented.

3. Advanced topics from graph coloring. Graph coloring belongs to basic graph invariants. We will study modern coloring concepts such as list coloring, choosability, and edge-colorings. A special attention will be paid to the Frequency Assignment Problem which motivated introduction of various distance constrained coloring variants.

4. Cuts and flows. The theory of network flows, minimax theorems, their applications to set systems (Hall theorem), and connectivity of graphs and networks.

5. Random graphs. Random graph models, their properties, and random graph evolution. Probabilistic proofs and algorithms. Pseudorandom graphs. Properties of the so-called web graph.

6. Graph visualisation. Methods and approaches used in Graph Drawing - planar graphs, drawing graphs with restricted edge intersections, drawing in a small grid. Visualisation of and searching in large graphs.

Syllabus of tutorials:

Study Objective:

Overview of modern methods of graph theory.

Study materials:

R. Diestel, Graph Theory, 3rd edition, Springer, 2005.

M.C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Freeman, New York 1980.

L. Kucera: Kombinatorické algoritmy, SNTL, 1989.

A. Schrijver: Combinatorial Optimization, Springer, 2003.

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Informatics (VO)