Advanced Topics in Computer Science (238900)
Winter semester 2005-06
last updated: 16.02.2006
Graph polynomials and graph decompositions, I
Slides of given lectures
For those graduate students who have already taken 238900 before,
but on another topic, arrangements will be found
to get credit again.
Lecturer: Prof. J.A. Makowsky and participants
Time: Tuesday, 10:30-12:30
Place: Taub 4
Prerequisites:
Computability, some elementary graph theory,
some familiarity with linear and abstract algebra.
Format:
Two hours frontal presentations.
Requirements:
Edited version of frontal presentation or
final project.
Outline
Graph polynomials
A common generalization of counting problems are graph polynomials.
The most prominent of these are the matching polynomials,
the colouring polynomials and the Tutte polynomial.
For general graphs these are often hard to compute (#P hard).
There are also various multivariate generalizations
of these polynomials.
Reducibilities between graph polynomials
Towards an algebraic complexity theory
Recursively constructed graphs
Tree-width, clique-width and beyond
Literature
- N. Biggs, Algebraic Graph Theory, Cambridge University Press
1973 (1993)
- F. Dong, K. Koh and K. Teo, Chromatic Polynomials and
chromaticity of graphs, World Scientific 2005
-
C. Godsil and G. Royle, Algebraic Graph Theory, Springer 2001
-
D. Welsh, Complexity: Knots, colourings and counting,
London Mathematical Society Lecture Note Series, vol. 186, 1993
- B. Bollobas, Modern Graph Theory, Springer 1998
- R. Diestel, Graph Theory, Springer 1997
- original papers