## DIMACS TR: 2003-03

## Chordal Bipartite Graphs of Bounded Tree- and Clique-width

### Authors: V. Lozin and D. Rautenbach

**
ABSTRACT
**

A bipartite graph is chordal bipartite
if every cycle of length at least six has a chord.
In the class of chordal bipartite graphs the
tree-width and the clique-width are unbounded.
Our main results are
that chordal bipartite graphs of bounded
vertex degree have bounded tree-width
and that $k$-fork-free chordal bipartite graphs
have bounded clique-width, where
a $k$-fork is the graph arising from a $K_{1,k+1}$
by subdividing one edge once. This implies
polynomial-time solvability for a variety of
algorithmical problems for these graphs.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-03.ps.gz

DIMACS Home Page