Minimal classes of graphs of unbounded clique-width
From MaRDI portal
Publication:659655
DOI10.1007/s00026-011-0117-2zbMath1234.05191OpenAlexW2153230366MaRDI QIDQ659655
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) 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 P4'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
