THICKNESS OF GRAPHS AND GRAPH DECOMPOSITIONS
Dr Ton Kloks, Department of Computer Science, Royal Holloway, University of London

Abstract: Consider a family $W$ of subsets of some ground set $S$. The thickness of $W$ is defined as $\inf_{\lambda}\sup_{w \in W} \lambda(w)$, where the infimum is taken over all non-negative weight functions $\lambda: S \rightarrow \Re{+}$ with $\lambda(S) = \sum_{x \in S} \lambda(x) = 1$. The thickness of a family of sets reflects certain aspects of the combinatorial structure of $W$. Notice that the thickness of a family of sets can be computed in polynomial time using linear programming.

For a graph $G=(V,E)$ we may consider different families of subsets of $V$, e.g., we can consider the edge set, the set of cycles, cliques, independent set, etc. I consider some possibilities.

Tree-decompositions have become a widely known and appreciated tool for solving all kinds of graph problems. A tree-decomposition of a graph $G$ is a pair $(S,T)$ where $T$ is a tree and $S$ a colection of subsets (called bags) of vertices, one for each node in $T$, such that every vertex and every edge of $G$ is in at least one bag and such that for every vertex $x$, the nodes of $T$ of which the bags contain $x$ form a subtree. I consider the smallest possible thickness of the family of bags taken over all tree-decompositions of $G$. It turns out to be $\frac{1}{\alpha(G)$, where $\alpha(G)$ is the maximum cardinality of a stable set in $G$.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 24 October 2001

back