DIMACS TR: 2002-54

On the band-, tree- and clique-width of graphs with bounded vertex degree

Authors: Vadim Lozin and Dieter Rautenbach


The band-, tree- and clique-width are of primary importance in algorithmic graph theory due to the fact that many problems being NP-hard for general graphs can be solved in polynomial time when restricted to graphs where one of these parameters is bounded. It is known that for any fixed $\Delta\geq 3$, all three parameters are unbounded for graphs with vertex degree at most $\Delta$. In this paper, we distinguish representative subclasses of graphs with bounded vertex degree that have bounded band-, tree- or clique-width. Our proofs are constructive and lead to efficient algorithms for a variety of NP-hard graph problems when restricted to those classes.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-54.ps.gz
DIMACS Home Page