Premium
Linear Clique‐Width for Hereditary Classes of Cographs
Author(s) -
Brignall Robert,
Korpelainen Nicholas,
Vatter Vincent
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22037
Subject(s) - combinatorics , mathematics , split graph , enumeration , clique , permutation (music) , discrete mathematics , cograph , permutation graph , bounded function , class (philosophy) , chordal graph , graph , 1 planar graph , computer science , mathematical analysis , physics , artificial intelligence , acoustics
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.