## Abstract

It is known that the class of graphs with treewidth (resp. pathwidth) bounded by a constant w can be characterized by a finite obstruction set obs(TW(w)) (resp. obs(PW(w))). These obstruction sets are known for w<=3 so far. In this paper we give a structural characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with a fixed number of vertices in terms of subgraphs of the complement. Our approach also essentially simplifies known characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with (w+3) vertices.

Also for any w>=3 a graph from obs(TW(w))-obs(PW(w)) is constructed, that solves an open problem.

Also for any w>=3 a graph from obs(TW(w))-obs(PW(w)) is constructed, that solves an open problem.

Original language | English |
---|---|

Pages (from-to) | 61-71 |

Journal | Discrete Applied Mathematics |

Volume | 120 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 15 Aug 2002 |

## Keywords

- Obstruction set
- Treewidth
- Pathwidth