Graphs of linear clique-width at most 3

DOI10.1016/J.TCS.2011.06.016MaRDI QIDQ719287zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Daniel Meister, Charis Papadopoulos

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

graphsclique-widthcharacterisationefficient recognition

Mathematics Subject Classification ID

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

Recommendations

• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Polynomial-time recognition of clique-width 3 graphs
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• Line graphs of bounded clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width

Cites work

• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Clique-width is NP-complete
• Domination on Cocomparability Graphs
• Efficient and practical algorithms for sequential modular decomposition
• Graph Classes: A Survey
• Handle-rewriting hypergraph grammars
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear layouts measuring neighbourhoods in graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Modular decomposition and transitive orientation
• 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)

• Clique-width of path powers
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Polynomial-time recognition of clique-width 3 graphs
• On the clique-width of graph with few \(P_{4}\)'s
• On characterizations for subclasses of directed co-graphs
• Clique-width and edge contraction
• A local characterization of bounded clique-width for line graphs
• Definable decompositions for graphs of bounded linear cliquewidth
• Linear rank-width and linear clique-width of trees
• Comparing linear width parameters for directed graphs
• Clique-width with an inactive label
• Definable decompositions for graphs of bounded linear cliquewidth
• Line graphs of bounded clique-width
• A characterisation of clique-width through nested partitions
• Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
• Vertex-transitive CIS graphs
• Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal
• Clique-width of full bubble model graphs
• Between clique-width and linear clique-width of bipartite graphs
• Linear clique-width for hereditary classes of cographs
• Neighbourhood-width of trees

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

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