Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs

DOI10.1016/J.DAM.2011.03.018MaRDI QIDQ415287zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Daniel Meister, Charis Papadopoulos

Publication date 11 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.03.018

zbMATH Keywords

characterization via forbidden induced subgraphsclique-widthspecial graph classes

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Graphs of linear clique-width at most 3
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• Linear clique-width for hereditary classes of cographs
• Fundamentals of Computation Theory
• Clique-width for 4-vertex forbidden subgraphs

Cites work

• A Complete Characterisation of the Linear Clique-Width of Path Powers
• A Linear Recognition Algorithm for Cographs
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Clique-width is NP-complete
• Graphs of Linear Clique-Width at Most 3
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• Linear layouts measuring neighbourhoods in graphs
• On the clique-width of some perfect graph classes
• On the Relationship Between Clique-Width and Treewidth
• On the relationship between NLC-width and linear NLC-width
• The relative clique-width of a graph
• Threshold graphs and related topics
• Upper bounds to the clique width of graphs

Cited in

(21)

• Grammars and clique-width bounds from split decompositions
• Between clique-width and linear clique-width of bipartite graphs
• Clique-width of full bubble model graphs
• Linear rank-width and linear clique-width of trees
• A characterisation of clique-width through nested partitions
• Colouring diamond-free graphs
• Linear clique-width for hereditary classes of cographs
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• Clique-width with an inactive label
• Neighbourhood-width of trees
• Several notions of rank-width for countable graphs
• Clique-width for graph classes closed under complementation
• Definable decompositions for graphs of bounded linear cliquewidth
• Bounding the clique-width of \(H\)-free split graphs
• Bounding the clique-width of \(H\)-free split graphs
• Graphs obtained by disjoint unions and joins of cliques and stable sets
• Graphs of linear clique-width at most 3
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• A local characterization of bounded clique-width for line graphs
• Classifying the clique-width of \(H\)-free bipartite graphs

This page was built for publication: Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs

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