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

DOI10.1016/j.dam.2011.03.018zbMath1238.05196OpenAlexW2060493079MaRDI QIDQ415287

Daniel Meister, Charis Papadopoulos, Pinar Heggernes

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

clique-widthspecial graph classescharacterization via forbidden induced subgraphs

Mathematics Subject Classification ID

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

Related Items (16)

Colouring diamond-free graphs ⋮ Grammars and clique-width bounds from split decompositions ⋮ Unnamed Item ⋮ A SAT Approach to Clique-Width ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Clique-width with an inactive label ⋮ Neighbourhood-width of trees ⋮ Several notions of rank-width for countable graphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Unnamed Item ⋮ Clique-width of full bubble model graphs ⋮ Linear rank-width and linear clique-width of trees ⋮ A characterisation of clique-width through nested partitions

Cites Work

• Unnamed Item
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Threshold graphs and related topics
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Linear layouts measuring neighbourhoods in graphs
• On the relationship between NLC-width and linear NLC-width
• The relative clique-width of a graph
• Graphs of Linear Clique-Width at Most 3
• Clique-Width is NP-Complete
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• A Linear Recognition Algorithm for Cographs
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth

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