Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs (Journal article)
Heggernes, P./ Meister, D./ Papadopoulos, C.
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. (C) 2011 Elsevier B.V. All rights reserved.
|Institution and School/Department of submitter:||Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών|
|Keywords:||clique-width,characterization via forbidden induced subgraphs,special graph classes,nlc-width,recognition|
|Link:||<Go to ISI>://000302981900015|
|Appears in Collections:||Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)|
Files in This Item:
|Heggernes-2012-Characterising the l.pdf||305.42 kB||Adobe PDF||View/Open Request a copy|
Please use this identifier to cite or link to this item:This item is a favorite for 0 people.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.