Recent developments on graphs of bounded clique-width

DOI10.1016/j.dam.2008.08.022zbMath1211.05165OpenAlexW2097725094MaRDI QIDQ967317

Vadim V. Lozin, Martin Milanič, Marcin Kaminski

Publication date: 28 April 2010

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

Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.022

zbMATH Keywords

clique-width tree-width hereditary class rank-width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70) Decidability of theories and sets of sentences (03B25) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Subgraph complementation and minimum rank, Eigenvalue location in graphs of small clique-width, Solving problems on generalized convex graphs via mim-width, The VC-dimension of graphs with respect to $k$-connected subgraphs, The rank-width of edge-coloured graphs, On Compiling Structured CNFs to OBDDs, Boundary classes for graph problems involving non-local properties, Colouring diamond-free graphs, Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs, The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring, Graph isomorphism for $(H_1, H_2)$-free graphs: an almost complete dichotomy, The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor, On quasi-planar graphs: clique-width and logical description, Well-quasi-order of relabel functions, On compiling structured CNFs to OBDDs, Colouring square-free graphs without long induced paths., Subgraph complementation, Bounding the Clique-Width of H-free Chordal Graphs, Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, On subgraph complementation to $H$-free graphs, Colouring of graphs with Ramsey-type forbidden subgraphs, Linear-time algorithms for three domination-based separation problems in block graphs, Bounding the mim‐width of hereditary graph classes, Clique‐width: Harnessing the power of atoms, Odd covers of graphs, Graph classes with and without powers of bounded clique-width, Bounding clique-width via perfect graphs, Compact labelings for efficient first-order model-checking, Cutting a tree with subgraph complementation is hard, except for some small trees, Clique-Width for Graph Classes Closed under Complementation, Classifying the clique-width of $H$-free bipartite graphs, Induced minor free graphs: isomorphism and clique-width, Linear Clique‐Width for Hereditary Classes of Cographs, Bounding the clique-width of $H$-free split graphs, The Small Set Vertex expansion problem, List $k$-colouring $P_t$-free graphs: a mim-width perspective, Solving problems on generalized convex graphs via mim-width, Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width, NP-hard graph problems and boundary classes of graphs, Computational complexity of the vertex cover problem in the class of planar triangulations, Polynomial-time algorithm for isomorphism of graphs with clique-width at most three, $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs, The behavior of clique-width under graph operations and graph transformations, Bounding the Mim-Width of Hereditary Graph Classes., Split permutation graphs, Unnamed Item, The Maximum Independent Set Problem in Planar Graphs, The $t$-latency bounded strong target set selection problem in some kinds of special family of graphs, Colouring Vertices of Triangle-Free Graphs, On the (parameterized) complexity of recognizing well-covered ($r$,$\ell$)-graph, Upper domination: towards a dichotomy through boundary properties, Compact representation of graphs of small clique-width, Clique-width and well-quasi-ordering of triangle-free graph classes, Bounding Clique-Width via Perfect Graphs, Bounding the clique-width of $H$-free split graphs, Unnamed Item, Graphs without large apples and the maximum weight independent set problem, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, A Boundary Property for Upper Domination, Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width, Colouring vertices of triangle-free graphs without forests, Colouring square-free graphs without long induced paths, Partial complementation of graphs, On subgraph complementation to $H$-free Graphs, Revising Johnson's table for the 21st century, The size‐Ramsey number of powers of bounded degree trees, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Clique-width and edge contraction, Exact solutions for latency-bounded target set selection problem on some special families of graphs

Cites Work