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
URI: https://olympias.lib.uoi.gr/jspui/handle/123456789/12615
ISSN: 0166-218X
Link: <Go to ISI>://000302981900015
http://ac.els-cdn.com/S0166218X11001120/1-s2.0-S0166218X11001120-main.pdf?_tid=eb5465616ed6f46d3b3f1dbbd0dcfc15&acdnat=1339409888_74318df27c42e98bc46387fc8c4e3c18
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:
https://olympias.lib.uoi.gr/jspui/handle/123456789/12615
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.