DIMACS TR: 2003-03

Chordal Bipartite Graphs of Bounded Tree- and Clique-width

Authors: V. Lozin and D. Rautenbach


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