Treewidth and small separators for graphs with small chordality
Hans L. Bodlaender, Dimitrios M. Thilikos · 1995
A graph G k-chordal, if it does not contain chordless cycles of length larger than k. The chordality cl of a graph G is the minimum k for which G is k-chordal. The degeneracy or the width of a graph is the maximum min-degree of any of its subgraphs. Our results are the following: 1. The problem of treewidth remains NP-complete when restricted on graphs with small maximum degree. 2. An upper bound is given for the treewidth of a graph as a function of its maximum degree and chordality. A consequence of this result is that when maximum degree and chordality are xed constants, then there is a linear algorithm for treewidth and a polynomial algorithm for pathwidth. 3. For any constant s 1, it is shown that any (s + 2)-chordal graph with degeneracy d contains a 1 2-separator of size O((dn) s,1 s), com-putable in linear time. Our results extent the many applications of the separator theorems in [1, 33, 34] to the class of k-chordal graphs. Several natural classes of graphs have small chordality. Weakly chordal graphs and cocomparability graphs are 4-chordal. We investigate the complexity of treewidth and pathwidth on these classes when an additional degree restriction is used. We present an application of our separator theorem on approximating the maximum independent set on k-chordal graphs with small degeneracy.