**
ACTA MATHEMATICA UNIVERSITATIS COMENIANAE **

Vol. 61, 2 (1992)

pp. 225-236

ON THE TREE-WIDTH OF A GRAPH

J. CHLEBIKOVA

**Abstract**.
Robertson and Seymour introduced the concept of the tree-width of a graph. It plays an important role in their results on graph minors culminating in their proof of Wagner's conjecture. This concept seems to be interesting from the algorithmic point of view as well: many graph problems that are NP-complete in general can be polynomially solvable if graphs are constrained to have bounded tree-width Ref. 2. In the present paper several equivalent definitions of tree-width are discussed and tree-width of several families of graphs is determined.

**AMS subject classification**.

**Keywords**.

**Download:** Adobe PDF Compressed Postscript

Acta Mathematica Universitatis Comenianae

Institute of Applied
Mathematics

Faculty of Mathematics,
Physics and Informatics

Comenius University

842 48 Bratislava, Slovak Republic

Telephone: + 421-2-60295111 Fax: + 421-2-65425882

e-Mail: amuc@fmph.uniba.sk
Internet: www.iam.fmph.uniba.sk/amuc
© Copyright 2001, ACTA MATHEMATICA
UNIVERSITATIS COMENIANAE