A graph G is k-chordal, if it does not contain chordless cycles of length larger than k. The chordality Ic 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 chordal@. A consequence of this result is that when maximum degree and chordal@ 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 i-separator of size O(n(S-')'S), computable in O(n3--("') ) time. Our results extent the many applications of the separator theorems in [l, 32,331 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.
Bodlaender et al. REF proved that the treewidth problem is NP-complete for graphs with small maximum degree.
Treewidth for graphs with small chordality
Discret. Appl. Math.
Discret. Appl. Math.
Mathematics Computer Science