Linear clique-width for hereditary classes of cographs

DOI10.1002/JGT.22037MaRDI QIDQ2978187zbMATH OpenOpenAlexFDO

Authors Robert Brignall, Nicholas Korpelainen, Vincent Vatter

Publication date 21 April 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.0636

zbMATH Keywords

cographslinear clique-widthquasi-threshold graphsthreshold graphs

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

Recommendations

• Between clique-width and linear clique-width of bipartite graphs
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Clique-width for hereditary graph classes
• Clique-width and the speed of hereditary properties
• Infinitely many minimal classes of graphs of unbounded clique-width

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• Approximating clique-width and branch-width
• Boolean-width of graphs
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Edge dominating set and colorings on graphs with fixed clique-width
• Graph Classes: A Survey
• Graphs of linear clique-width at most 3
• Handle-rewriting hypergraph grammars
• Induced subgraphs and well‐quasi‐ordering
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimal classes of graphs of unbounded clique-width
• On the Relationship Between Clique-Width and Treewidth
• On the relationship between NLC-width and linear NLC-width
• Recent developments on graphs of bounded clique-width
• Subclasses of the separable permutations
• Sur l'extension aux relations de quelques propriétés des ordres
• The theory of well-quasi-ordering: a frequently discovered concept
• Upper bounds to the clique width of graphs

Cited in

(17)

• Clique-width and the speed of hereditary properties
• Critical properties and complexity measures of read-once Boolean functions
• Between clique-width and linear clique-width of bipartite graphs
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• Infinitely many minimal classes of graphs of unbounded clique-width
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• Clique-width with an inactive label
• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• Tree pivot-minors and linear rank-width
• The Micro-world of Cographs
• Bounding the mim‐width of hereditary graph classes
• A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
• Graphs of linear growth have bounded treewidth
• Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
• The micro-world of cographs
• A local characterization of bounded clique-width for line graphs

This page was built for publication: Linear clique-width for hereditary classes of cographs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978187)