Hdl Handle:
http://hdl.handle.net/10545/621048
Title:
Linear clique-width for hereditary classes of cographs
Authors:
Brignall, Robert; Korpelainen, Nicholas ( 0000-0001-7142-9515 ) ; Vatter, Vincent
Abstract:
The class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contain all quasi-threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.
Affiliation:
University of Derby
Citation:
Brignall, R. et al (2016) 'Linear Clique-Width for Hereditary Classes of Cographs' Journal of Graph Theory, 84 (4), pp. 501-511. DOI: 10.1002/jgt.22037
Publisher:
Wiley
Journal:
Journal of Graph Theory
Issue Date:
28-Mar-2016
URI:
http://hdl.handle.net/10545/621048
DOI:
10.1002/jgt.22037
Additional Links:
http://doi.wiley.com/10.1002/jgt.22037
Type:
Article
Language:
en
ISSN:
0364-9024
Appears in Collections:
Department of Electronics, Computing & Maths

Full metadata record

DC FieldValue Language
dc.contributor.authorBrignall, Roberten
dc.contributor.authorKorpelainen, Nicholasen
dc.contributor.authorVatter, Vincenten
dc.date.accessioned2016-11-23T15:08:46Z-
dc.date.available2016-11-23T15:08:46Z-
dc.date.issued2016-03-28-
dc.identifier.citationBrignall, R. et al (2016) 'Linear Clique-Width for Hereditary Classes of Cographs' Journal of Graph Theory, 84 (4), pp. 501-511. DOI: 10.1002/jgt.22037en
dc.identifier.issn0364-9024-
dc.identifier.doi10.1002/jgt.22037-
dc.identifier.urihttp://hdl.handle.net/10545/621048-
dc.description.abstractThe class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contain all quasi-threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.en
dc.language.isoenen
dc.publisherWileyen
dc.relation.urlhttp://doi.wiley.com/10.1002/jgt.22037en
dc.rightsArchived with thanks to Journal of Graph Theoryen
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.subjectCographen
dc.subjectGraph theoryen
dc.subjectClique-widthen
dc.subjectGraph classen
dc.titleLinear clique-width for hereditary classes of cographsen
dc.typeArticleen
dc.contributor.departmentUniversity of Derbyen
dc.identifier.journalJournal of Graph Theoryen
dc.contributor.institutionDEPARTMENT OF MATHEMATICS AND STATISTICS; THE OPEN UNIVERSITY; MILTON KEYNES UNITED KINGDOM-
dc.contributor.institutionMATHEMATICS DEPARTMENT; UNIVERSITY OF DERBY; DERBY UNITED KINGDOM-
dc.contributor.institutionDEPARTMENT OF MATHEMATICS; UNIVERSITY OF FLORIDA; GAINESVILLE FL UNITED STATES OF AMERICA-
This item is licensed under a Creative Commons License
Creative Commons
All Items in UDORA are protected by copyright, with all rights reserved, unless otherwise indicated.