Show simple item record

dc.contributor.authorBrignall, Robert
dc.contributor.authorKorpelainen, Nicholas
dc.contributor.authorVatter, Vincent
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.
dc.language.isoenen
dc.publisherWileyen
dc.relation.urlhttp://doi.wiley.com/10.1002/jgt.22037en
dc.relation.urlhttps://arxiv.org/abs/1305.0636
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
html.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.


This item appears in the following Collection(s)

Show simple item record

Archived with thanks to Journal of Graph Theory
Except where otherwise noted, this item's license is described as Archived with thanks to Journal of Graph Theory