Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420191 | Discrete Applied Mathematics | 2012 | 14 Pages |
Abstract
We study the linear clique-width of graphs that are obtained from paths by disjoint union and adding true twins. We show that these graphs have linear clique-width at most 4, and we give a complete characterisation of their linear clique-width by forbidden induced subgraphs. As a consequence, we obtain a linear-time algorithm for computing the linear clique-width of the considered graphs. Our results extend the previously known set of forbidden induced subgraphs for graphs of linear clique-width at most 3.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Pinar Heggernes, Daniel Meister, Charis Papadopoulos,