Minimal classes of graphs of unbounded clique-width
From MaRDI portal
Publication:659655
DOI10.1007/S00026-011-0117-2zbMATH Open1234.05191OpenAlexW2153230366MaRDI QIDQ659655FDOQ659655
Authors: Vadim 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
Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)
Cites Work
- Optimal path cover problem on block graphs and bipartite permutation graphs
- Proper interval graphs and the guard problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Title not available (Why is that?)
- On the clique-width of some perfect graph classes
- Title not available (Why is that?)
- Title not available (Why is that?)
- The strong perfect graph theorem
- Graph minors. V. Excluding a planar graph
- Bipartite permutation graphs
- Bandwidth of chain graphs
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- Diameter and treewidth in minor-closed graph families
- Clique-width for 4-vertex forbidden subgraphs
- Local tree-width, excluded minors, and approximation algorithms
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Difference graphs
- Decompositions for the edge colouring of reduced indifference graphs.
- Title not available (Why is that?)
- Edge dominating set and colorings on graphs with fixed clique-width
- Precoloring extension on unit interval graphs
- A Fully dynamic algorithm for recognizing and representing proper interval graphs
- THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
- On the clique-width of graph with few \(P_{4}\)'s
- Diameter and treewidth in minor-closed graph families, revisited
- A short proof that `proper = unit'
- Chordal bipartite graphs of bounded tree- and clique-width
- Graph-Theoretic Concepts in Computer Science
- SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
- Title not available (Why is that?)
- NP-completeness results for some problems on subclasses of bipartite and chordal graphs
- An interval graph is a comparability graph
- On semi-\(P_ 4\)-sparse graphs
- Clique-width minimization is NP-hard
- Jump number maximization for proper interval graphs and series-parallel graphs
Cited In (23)
- On low rank-width colorings
- Clique-width of path powers
- Critical properties of bipartite permutation graphs
- Infinitely many minimal classes of graphs of unbounded clique-width
- Uncountably many minimal hereditary classes of graphs of unbounded clique-width
- Minor-Closed Graph Classes with Bounded Layered Pathwidth
- A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
- \(t\)-sails and sparse hereditary classes of unbounded tree-width
- MSO undecidability for hereditary classes of unbounded clique-width
- Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
- Bichain graphs: geometric model and universal graphs
- Graph classes with and without powers of bounded clique-width
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- 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
- Between clique-width and linear clique-width of bipartite graphs
- Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
- Linear clique-width for hereditary classes of cographs
- Canonical antichains of unit interval and bipartite permutation graphs
- A new graph construction of unbounded clique-width
- Rationality for subclasses of 321-avoiding permutations
- Split permutation graphs
- Title not available (Why is that?)
This page was built for publication: Minimal classes of graphs of unbounded clique-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659655)
