Treewidth for graphs with small chordality

A graph G is k-chordal, if it does not contain chordless cycles of length larger than k. The chordality lc 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 to 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 fixed 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 bounded width contains an 1/2-separator of size O(n^(s-1)/s), computable in O(n^3-(1/s)) time. Our results extent the many applications of the separator theorems in [1, 32, 33] 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 width.