Linear Clique‐Width for Hereditary Classes of Cographs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Linear Clique‐Width for Hereditary Classes of Cographs

Authors:	Robert Brignall Nicholas Korpelainen Vincent Vatter

Institution:	1. DEPARTMENT OF MATHEMATICS AND STATISTICS, THE OPEN UNIVERSITY, MILTON KEYNES, UNITED KINGDOMContract grant sponsor: EPSRC;2. contract grant number: EP/J006130/1;3. Contract grant sponsor: NSA;4. contract grant number: H98230‐12‐1‐0207;5. Contract grant sponsor: NSF;6. contract grant number: DMS‐1301692. The United States Government is authorized to reproduce and distribute reprints not‐withstanding any copyright notation herein.;7. MATHEMATICS DEPARTMENT, UNIVERSITY OF DERBY, DERBY, UNITED KINGDOM;8. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF FLORIDA, GAINESVILLE, UNITED STATES OF AMERICA

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.

Keywords:	linear clique‐width cographs threshold graphs quasi‐threshold graphs clique‐width