Critical properties of bipartite permutation graphs

DOI10.1002/jgt.23011zbMath1530.05129arXiv2010.14467OpenAlexW3095962291MaRDI QIDQ6142657

Bogdan Alecu, Vadim V. Lozin, Dmitriy S. Malyshev

Publication date: 4 January 2024

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.14467

zbMATH Keywords

well-quasi-orderinguniversal graphinduced subgraph isomorphismbipartite permutation graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A complexity dichotomy and a new boundary class for the dominating set problem
• Boundary properties of well-quasi-ordered sets of graphs
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Critical hereditary graph classes: a survey
• Boundary properties of graphs for algorithmic graph problems
• Canonical antichains of unit interval and bipartite permutation graphs
• Minimal classes of graphs of unbounded clique-width
• Bipartite permutation graphs with application to the minimum buffer size problem
• Graph minors. XX: Wagner's conjecture
• On low tree-depth decompositions
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• Graph minors. V. Excluding a planar graph
• Bipartite permutation graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Letter graphs and well-quasi-order by induced subgraphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Graph parameters and Ramsey theory
• Algorithmic meta-theorems for restrictions of treewidth
• The speed of hereditary properties of graphs
• Boundary classes of graphs for the dominating set problem
• Upper bounds to the clique width of graphs
• Integer conic function minimization based on the comparison oracle
• Parikh word representability of bipartite permutation graphs
• A polynomial algorithm for minimizing discrete convic functions in fixed dimension
• Branch-depth: generalizing tree-depth of graphs
• Two forbidden induced subgraphs and well-quasi-ordering
• A dichotomy for minimum cost graph homomorphisms
• NP-hard graph problems and boundary classes of graphs
• Level of repair analysis and minimum cost homomorphisms of graphs
• A jump to the Bell number for hereditary graph properties
• Rank-width and vertex-minors
• Structural properties of word representable graphs
• Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
• Integer Programming with a Fixed Number of Variables
• BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE
• Boundary Classes of Planar Graphs
• Minkowski's Convex Body Theorem and Integer Programming
• Interval bigraphs and circular arc graphs
• The Micro-world of Cographs
• Well‐quasi‐ordering and finite distinguishing number
• On the Lettericity of Paths
• Containing All Permutations
• Small Superpatterns for Dominance Drawing
• Deciding the Bell Number for Hereditary Graph Properties
• Quasimonotone graphs

This page was built for publication: Critical properties of bipartite permutation graphs