Details

Autor(en) / Beteiligte

• Gurski, Frank
• Wanke, Egon

Titel

Line graphs of bounded clique-width

Ist Teil von

• Discrete mathematics, 2007-10, Vol.307 (22), p.2734-2754

Ort / Verlag

Amsterdam: Elsevier B.V

Erscheinungsjahr

2007

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

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