The relative clique-width of a graph

DOI10.1016/j.jctb.2007.04.001zbMath1123.05064OpenAlexW2025013668MaRDI QIDQ2642017

Vadim V. 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

zbMATH Keywords

approximation algorithmcolouringchromatic numberclique-widthtree-widthtree-decomposition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (18)

Clique-width of path powers ⋮ Identifying codes in the complementary prism of cycles ⋮ The relative clique-width of a graph ⋮ The rank-width of edge-coloured graphs ⋮ A SAT Approach to Clique-Width ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs ⋮ Clique-width with an inactive label ⋮ Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width ⋮ Well-quasi-ordering versus clique-width ⋮ On a disparity between relative cliquewidth and relative NLC-width ⋮ Graphs of linear clique-width at most 3 ⋮ Well-quasi-ordering Does Not Imply Bounded Clique-width ⋮ Graph operations characterizing rank-width ⋮ On the relationship between NLC-width and linear NLC-width ⋮ Clique-width of full bubble model graphs ⋮ Linear rank-width and linear clique-width of trees ⋮ A characterisation of clique-width through nested partitions

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Clique-width of countable graphs: A compactness property.
• 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
• Rank-width and vertex-minors
• On the relationship between NLC-width and linear NLC-width
• The relative clique-width of a graph
• Clique-width minimization is NP-hard
• Graph minors. II. Algorithmic aspects of tree-width
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The relative clique-width of a graph