Minimal classes of graphs of unbounded clique-width

DOI10.1007/s00026-011-0117-2zbMath1234.05191MaRDI 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 tractability; clique-width; unit interval graphs; bipartite permutation graphs

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C75: Structural characterization of families of graphs

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Canonical antichains of unit interval and bipartite permutation graphs, Split permutation graphs

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