The relative clique-width of a graph
DOI10.1016/J.JCTB.2007.04.001zbMATH Open1123.05064OpenAlexW2025013668MaRDI QIDQ2642017FDOQ2642017
Vadim Lozin, Dieter Rautenbach
Publication date: 20 August 2007
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2007.04.001
Recommendations
- scientific article; zbMATH DE number 2044924
- On the Relationship Between Clique-Width and Treewidth
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- On a disparity between relative cliquewidth and relative NLC-width
- Clique-width is NP-complete
- Clique-width minimization is NP-hard
- A characterisation of clique-width through nested partitions
- From tree-decompositions to clique-width terms
- scientific article; zbMATH DE number 1830724
- Deciding Clique-Width for Graphs of Bounded Tree-Width
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- The relative clique-width of a graph
- Title not available (Why is that?)
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Rank-width and vertex-minors
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Clique-width of countable graphs: A compactness property.
- On the relationship between NLC-width and linear NLC-width
- Title not available (Why is that?)
- Clique-width minimization is NP-hard
Cited In (27)
- Clique-width of path powers
- On the Relationship Between Clique-Width and Treewidth
- Graphs of linear clique-width at most 3
- Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
- Computing the clique-width of cactus graphs
- Well-quasi-ordering versus clique-width
- On a disparity between relative cliquewidth and relative NLC-width
- Identifying codes in the complementary prism of cycles
- Title not available (Why is that?)
- Compact representation of graphs of small clique-width
- Clique-width of countable graphs: A compactness property.
- Linear rank-width and linear clique-width of trees
- A SAT Approach to Clique-Width
- Line graphs of bounded clique-width
- Clique-width with an inactive label
- A characterisation of clique-width through nested partitions
- Graph operations characterizing rank-width
- Clique width of partner limited graphs
- The relative clique-width of a graph
- Clique-width of point configurations
- On the relationship between NLC-width and linear NLC-width
- Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width
- Clique-width of full bubble model graphs
- Vertex-minors of graphs: a survey
- Between clique-width and linear clique-width of bipartite graphs
- Well-quasi-ordering Does Not Imply Bounded Clique-width
- The rank-width of edge-coloured graphs
This page was built for publication: The relative clique-width of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2642017)
