Critical properties of bipartite permutation graphs
From MaRDI portal
Abstract: The class of bipartite permutation graphs enjoys many nice and important properties. In particular, this class is critically important in the study of clique- and rank-width of graphs, because it is one of the minimal hereditary classes of graphs of unbounded clique- and rank-width. It also contains a number of important subclasses, which are critical with respect to other parameters, such as graph lettericity or shrub-depth, and with respect to other notions, such as well-quasi-ordering or complexity of algorithmic problems. In the present paper we identify critical subclasses of bipartite permutation graphs of various types.
Recommendations
Cites work
- A complexity dichotomy and a new boundary class for the dominating set problem
- A dichotomy for minimum cost graph homomorphisms
- A jump to the Bell number for hereditary graph properties
- A polynomial algorithm for minimizing discrete convic functions in fixed dimension
- Algorithmic meta-theorems for restrictions of treewidth
- Bipartite permutation graphs
- Bipartite permutation graphs are reconstructible
- Bipartite permutation graphs with application to the minimum buffer size problem
- Boundary classes of graphs for the dominating set problem
- Boundary Classes of Planar Graphs
- Boundary properties of graphs for algorithmic graph problems
- Boundary properties of well-quasi-ordered sets of graphs
- Branch-depth: generalizing tree-depth of graphs
- Canonical antichains of unit interval and bipartite permutation graphs
- Containing all permutations
- Critical hereditary graph classes: a survey
- Deciding the Bell number for hereditary graph properties
- Graph minors. V. Excluding a planar graph
- Graph minors. XX: Wagner's conjecture
- Graph parameters and Ramsey theory
- scientific article; zbMATH DE number 5720940 (Why is no real title available?)
- scientific article; zbMATH DE number 139780 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1286524 (Why is no real title available?)
- scientific article; zbMATH DE number 7029306 (Why is no real title available?)
- Induced subgraph isomorphism on proper interval and bipartite permutation graphs
- Integer conic function minimization based on the comparison oracle
- Integer Programming with a Fixed Number of Variables
- Interval bigraphs and circular arc graphs
- Letter graphs and well-quasi-order by induced subgraphs
- Level of repair analysis and minimum cost homomorphisms of graphs
- Linear time algorithm for computing a small biclique in graphs without long induced paths
- Minimal classes of graphs of unbounded clique-width
- Minkowski's Convex Body Theorem and Integer Programming
- NP-completeness results for some problems on subclasses of bipartite and chordal graphs
- NP-hard graph problems and boundary classes of graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On low tree-depth decompositions
- On the Lettericity of Paths
- Parikh word representability of bipartite permutation graphs
- Quasimonotone graphs
- Rank-width and vertex-minors
- Small superpatterns for dominance drawing
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Structural properties of word representable graphs
- The Micro-world of Cographs
- The speed of hereditary properties of graphs
- Two forbidden induced subgraphs and well-quasi-ordering
- Upper bounds to the clique width of graphs
- Well‐quasi‐ordering and finite distinguishing number
This page was built for publication: Critical properties of bipartite permutation graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6142657)
