Graphs of linear clique-width at most 3

DOI10.1016/j.tcs.2011.06.016zbMath1225.68135OpenAlexW2137616550MaRDI QIDQ719287

Pinar Heggernes, Charis Papadopoulos, Daniel Meister

Publication date: 10 October 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.06.016

zbMATH Keywords

characterisationgraphsclique-widthefficient recognition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

Clique-width of path powers ⋮ Unnamed Item ⋮ A SAT Approach to Clique-Width ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ Linear Clique‐Width for Hereditary Classes of Cographs ⋮ Clique-width with an inactive label ⋮ Vertex-transitive CIS graphs ⋮ Neighbourhood-width of trees ⋮ On characterizations for subclasses of directed co-graphs ⋮ Comparing linear width parameters for directed graphs ⋮ Linear rank-width and linear clique-width of trees ⋮ A characterisation of clique-width through nested partitions ⋮ Clique-width and edge contraction

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Modular decomposition and transitive orientation
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Threshold graphs and related topics
• Linear time solvable optimization problems on graphs of bounded clique-width
• 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
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Domination on Cocomparability Graphs
• Clique-Width is NP-Complete
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey

This page was built for publication: Graphs of linear clique-width at most 3