Clique-width with an inactive label

DOI10.1016/J.DISC.2014.08.005MaRDI QIDQ465271zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)