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
ISSN: 0166-218X
Link: <Go to ISI>://000302981900015
Publisher: Elsevier
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Files in This Item:
File Description SizeFormat 
Heggernes-2012-Characterising the l.pdf305.42 kBAdobe PDFView/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.