The structure of obstructions to treewidth and pathwidth

Janka Chlebikova

doi:10.1016/S0166-218X(01)00281-5

The structure of obstructions to treewidth and pathwidth

Janka Chlebikova

School of Computing

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	61-71
Journal	Discrete Applied Mathematics
Volume	120
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(01)00281-5
Publication status	Published - 15 Aug 2002

Keywords

Obstruction set
Treewidth
Pathwidth

Access to Document

10.1016/S0166-218X(01)00281-5

Cite this

@article{e42930ca2c464c9eb6082051dca82c3d,

title = "The structure of obstructions to treewidth and pathwidth",

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.",

keywords = "Obstruction set, Treewidth, Pathwidth",

author = "Janka Chlebikova",

year = "2002",

month = aug,

day = "15",

doi = "10.1016/S0166-218X(01)00281-5",

language = "English",

volume = "120",

pages = "61--71",

journal = "Discrete Applied Mathematics",

number = "1-3",

}

TY - JOUR

T1 - The structure of obstructions to treewidth and pathwidth

AU - Chlebikova, Janka

PY - 2002/8/15

Y1 - 2002/8/15

N2 - 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.

AB - 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.

KW - Obstruction set

KW - Treewidth

KW - Pathwidth

U2 - 10.1016/S0166-218X(01)00281-5

DO - 10.1016/S0166-218X(01)00281-5

M3 - Article

VL - 120

SP - 61

EP - 71

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

The structure of obstructions to treewidth and pathwidth

Abstract

Keywords

Access to Document

Fingerprint

Cite this