Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
DOI10.1016/J.DAM.2011.03.018zbMATH Open1238.05196OpenAlexW2060493079MaRDI QIDQ415287FDOQ415287
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
Recommendations
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Threshold graphs and related topics
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- Linear layouts measuring neighbourhoods in graphs
- The relative clique-width of a graph
- Clique-width is NP-complete
- A Complete Characterisation of the Linear Clique-Width of Path Powers
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- On the Relationship Between Clique-Width and Treewidth
- A Linear Recognition Algorithm for Cographs
- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- On the relationship between NLC-width and linear NLC-width
- Graphs of Linear Clique-Width at Most 3
- Title not available (Why is that?)
Cited In (20)
- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- Graphs of linear clique-width at most 3
- Clique-Width for Graph Classes Closed under Complementation
- Title not available (Why is that?)
- A local characterization of bounded clique-width for line graphs
- Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
- Bounding the clique-width of \(H\)-free split graphs
- Linear rank-width and linear clique-width of trees
- Colouring diamond-free graphs
- A SAT Approach to Clique-Width
- Clique-width with an inactive label
- A characterisation of clique-width through nested partitions
- Bounding the clique-width of \(H\)-free split graphs
- Classifying the clique-width of \(H\)-free bipartite graphs
- Grammars and clique-width bounds from split decompositions
- Clique-width of full bubble model graphs
- Between clique-width and linear clique-width of bipartite graphs
- Neighbourhood-width of trees
- Several notions of rank-width for countable graphs
- Title not available (Why is that?)
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)
