Graphs of linear clique-width at most 3 (Journal article)
Papadopoulos, C./ Heggernes, P./ Meister, D.
A graph has linear clique-width at most k if it has a clique-width expression using at most k labels such that every disjoint union operation has an operand which is a single vertex graph. We give the first characterisation of graphs of linear clique-width at most 3, and we give the first polynomial-time recognition algorithm for graphs of linear clique-width at most 3. In addition, we present new characterisations of graphs of linear clique-width at most 2. We also give a layout characterisation of graphs of bounded linear clique-width; a similar characterisation was independently shown by Gurski and by Lozin and Rautenbach
|Institution and School/Department of submitter:||Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών|
|Appears in Collections:||Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)|
Files in This Item:
|Papadopoulos-2011-graphs of linear.pdf||393.71 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.