Ilia Averbouch, Ph.D. Thesis Seminar
Wednesday, 20.10.2010, 14:00
Graph polynomials are powerful and well-developed tools to express graph
parameters. Usually graph polynomials are compared to each other by ad-hoc means
allowing to decide whether a newly defined graph polynomial generalizes
(or is generalized) by another one.
We study their distinctive power and
introduce the notions of $dp$-completeness and universality of graph
polynomials in order to formalize dependencies between them.
Many known graph polynomials satisfy linear recurrence relations with
respect to some set of edge- or vertex-elimination operations.
Inspired by the work of Brylawski and Oxley on the Tutte polynomial,
we define several classes of graph polynomials according to their
recurrence relations, and prove $dp$-completeness and universality
results for those classes.
The talk is self-contained and does not require any prior knowledge
on graph polynomials.