DIMACS TR: 2002-54
On the band-, tree- and clique-width of graphs with bounded vertex degree
Authors: Vadim Lozin and Dieter Rautenbach
ABSTRACT
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