Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Elsevier
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Discrete Applied Mathematics
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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.
Περιγραφή
Λέξεις-κλειδιά
clique-width, characterization via forbidden induced subgraphs, special graph classes, nlc-width, recognition
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000302981900015
http://ac.els-cdn.com/S0166218X11001120/1-s2.0-S0166218X11001120-main.pdf?_tid=eb5465616ed6f46d3b3f1dbbd0dcfc15&acdnat=1339409888_74318df27c42e98bc46387fc8c4e3c18
http://ac.els-cdn.com/S0166218X11001120/1-s2.0-S0166218X11001120-main.pdf?_tid=eb5465616ed6f46d3b3f1dbbd0dcfc15&acdnat=1339409888_74318df27c42e98bc46387fc8c4e3c18
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών