#
Research Seminar in Combinatorics and Graph Theory (238902)

Winter semester 2011/12

last updated: **22.10.2011**

Announced as 238901 (because the course 238902 is still awaiting
senate approval).
##
Structural Graph Theory and Algorithmic Meta-theorems

**NEW (tba)**:
List of topics for seminar talks.
**NEW (tba)**:
Slides of given lectures

For those graduate students who have already taken 238901 before,

but on another topic, arrangements will be found
to get credit again.

** Lecturer: ** Prof. J.A. Makowsky and participants

**NEW TIME: ** Sunday, 12:30-14:30

**New Place:** Taub 4

**Prerequisites:**
Some elementary graph theory,
Computability.

**Format:**
Two hours frontal presentations.

**Requirements:**
Edited version of frontal presentation or
final project.

#### Outline

One of the great achievements in graph theory is the
emergence of a **structural theory** initiated by the work
of
N. Robertson and P. Seymour and their students and collaborators.
The prototype of a structural theorem concerns the characterization of
minor closed graph classes and the notion of tree-width of a graph.
More recently, other notions of width emerged, such as clique-width and
rank-width, for which there are also structural theorems.
The basic theory is well covered in the book
Graph Theory by R. Diestel.

The structural theory of graphs also led to
**algorithmic meta-theorems**, theorems of the form

###
Every problem of the from xxxxx has certain algorithmic properties

Here xxxxx can be a definability condition like
contsraint satisfaction problems, classes of graphs of fixed width
definable in some formalism, etc.
A survey of such theorems can befound in my recently edited
book,
available on line,
in particular the paper by
http://www.cs.technion.ac.il/~janos/COURSES/238902-11/
The first meeting of the seminar is on
##
Sunday, 30 October, 12:30, Taub 4

Feel free to contact me before that if you have any questions.