Minimal classes of graphs of unbounded clique-width
From MaRDI portal
Publication:659655
DOI10.1007/s00026-011-0117-2zbMath1234.05191MaRDI 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
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
On low rank-width colorings, Clique-width of path powers, A new graph construction of unbounded clique-width, Canonical antichains of unit interval and bipartite permutation graphs, Graph classes with and without powers of bounded clique-width, Bichain graphs: geometric model and universal graphs, Split permutation graphs, 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, Uncountably many minimal hereditary classes of graphs of unbounded clique-width, Between clique-width and linear clique-width of bipartite graphs, Classes of graphs with low complexity: the case of classes with bounded linear rankwidth, Infinitely many minimal classes of graphs of unbounded clique-width, Rationality for subclasses of 321-avoiding permutations, Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs, Linear Clique‐Width for Hereditary Classes of Cographs
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