Clique-width with an inactive label

DOI10.1016/J.DISC.2014.08.005zbMATH Open1301.05108OpenAlexW2048502143MaRDI QIDQ465271FDOQ465271

Authors: Daniel Meister 

Publication date: 31 October 2014

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

Full work available at URL: https://doi.org/10.1016/j.disc.2014.08.005

Recommendations

• Graphs of linear clique-width at most 3
• Inductive computations on graphs defined by clique-width expressions
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Constrained-path labellings on graphs of bounded clique-width
• The relative clique-width of a graph

zbMATH Keywords

clique-widthdistance-hereditary graphsforbidden induced subgraphscharacterisationlinear clique-width

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Complement reducible graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Linear layouts measuring neighbourhoods in graphs
• The relative clique-width of a graph
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Clique-width is NP-complete
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Graphs of linear clique-width at most 3
• Distance-hereditary graphs
• Rank-width and vertex-minors
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Claw-free graphs. III: Circular interval graphs
• On the relationship between NLC-width and linear NLC-width
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Completely separable graphs
• Obstructions for linear rank-width at most 1
• Linear Rank-Width and Linear Clique-Width of Trees
• Linear Clique‐Width for Hereditary Classes of Cographs

Cited In (3)

• Linear rank-width and linear clique-width of trees
• Grammars and clique-width bounds from split decompositions
• Clique-width of full bubble model graphs

This page was built for publication: Clique-width with an inactive label

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