Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650288 | Discrete Mathematics | 2007 | 21 Pages |
Abstract
We show that a set of graphs has bounded tree-width or bounded path-width if and only if the corresponding set of line graphs has bounded clique-width or bounded linear clique-width, respectively. This relationship implies some interesting algorithmic properties and re-proves already known results in a very simple way. It also shows that the minimization problem for NLC-width is NP-complete.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Frank Gurski, Egon Wanke,