Minimal classes of graphs of unbounded clique-width

DOI10.1007/S00026-011-0117-2zbMath1234.05191OpenAlexW2153230366MaRDI QIDQ659655

Vadim V. Lozin

Publication date: 24 January 2012

Published in: Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00026-011-0117-2

zbMATH Keywords

fixed parameter tractabilityclique-widthunit interval graphsbipartite permutation graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (19)

Clique-width of path powers ⋮ Uncountably many minimal hereditary classes of graphs of unbounded clique-width ⋮ Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs ⋮ Infinitely many minimal classes of graphs of unbounded clique-width ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width ⋮ Rationality for subclasses of 321-avoiding permutations ⋮ Graph classes with and without powers of bounded clique-width ⋮ Bichain graphs: geometric model and universal graphs ⋮ Critical properties of bipartite permutation graphs ⋮ Linear Clique‐Width for Hereditary Classes of Cographs ⋮ Canonical antichains of unit interval and bipartite permutation graphs ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ A new graph construction of unbounded clique-width ⋮ Split permutation graphs ⋮ Unnamed Item ⋮ On low rank-width colorings ⋮ On the maximum cardinality cut problem in proper interval graphs and related graph classes ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bandwidth of chain graphs
• The strong perfect graph theorem
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• Graph minors. V. Excluding a planar graph
• Bipartite permutation graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• A short proof that `proper = unit'
• On semi-\(P_ 4\)-sparse graphs
• Proper interval graphs and the guard problem
• Decompositions for the edge colouring of reduced indifference graphs.
• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• Jump number maximization for proper interval graphs and series-parallel graphs
• Chordal bipartite graphs of bounded tree- and clique-width
• Edge dominating set and colorings on graphs with fixed clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Clique-width for 4-vertex forbidden subgraphs
• Precoloring extension on unit interval graphs
• Local tree-width, excluded minors, and approximation algorithms
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• Clique-width minimization is NP-hard
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• Approximation algorithms for NP-complete problems on planar graphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• An interval graph is a comparability graph
• Difference graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Minimal classes of graphs of unbounded clique-width