Geodesic
ON THE TREE-WIDTH OF A GRAPH
Acta mathematica Universitatis Comenianae, Tome 61 (1992) no. 2 
J. Chlebikova. ON THE TREE-WIDTH OF A GRAPH. Acta mathematica Universitatis Comenianae, Tome 61 (1992) no. 2. http://geodesic.mathdoc.fr/item/AMUC_1992_61_2_a8/
@article{AMUC_1992_61_2_a8,
     author = {J. Chlebikova},
     title = {ON {THE} {TREE-WIDTH} {OF} {A} {GRAPH}},
     journal = {Acta mathematica Universitatis Comenianae},
     year = {1992},
     volume = {61},
     number = {2},
     url = {http://geodesic.mathdoc.fr/item/AMUC_1992_61_2_a8/}
}
TY  - JOUR
AU  - J. Chlebikova
TI  - ON THE TREE-WIDTH OF A GRAPH
JO  - Acta mathematica Universitatis Comenianae
PY  - 1992
VL  - 61
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/AMUC_1992_61_2_a8/
ID  - AMUC_1992_61_2_a8
ER  - 
%0 Journal Article
%A J. Chlebikova
%T ON THE TREE-WIDTH OF A GRAPH
%J Acta mathematica Universitatis Comenianae
%D 1992
%V 61
%N 2
%U http://geodesic.mathdoc.fr/item/AMUC_1992_61_2_a8/
%F AMUC_1992_61_2_a8

Voir la notice de l'article provenant de la source Comenius University

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.