Two characterisations of the minimal triangulations of permutation graphs
From MaRDI portal
Publication:390311
DOI10.1016/j.disc.2013.06.004zbMath1281.05057MaRDI QIDQ390311
Publication date: 23 January 2014
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2013.06.004
interval graphs; permutation graphs; characterisations; minimal triangulations; potential maximal cliques
05C35: Extremal problems in graph theory
05A05: Permutations, words, matrices
05C10: Planar graphs; geometric and topological aspects of graph theory
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bandwidth on AT-free graphs
- Treewidth and minimum fill-in on permutation graphs in linear time
- On rigid circuit graphs
- Minimal triangulations of graphs: a survey
- Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs
- On a property of minimal triangulations
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Listing all potential maximal cliques of a graph
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- A characterisation of rigid circuit graphs
- Triangulating graphs without asteroidal triples
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Finding Induced Subgraphs via Minimal Triangulations
- Graph minors. II. Algorithmic aspects of tree-width
- Representations of chordal graphs as subtrees of a tree
- Algorithmic Aspects of Vertex Elimination on Graphs
- Graph Classes: A Survey
- The Pathwidth and Treewidth of Cographs
- Approximating the Bandwidth for Asteroidal Triple-Free Graphs
- Treewidth and Pathwidth of Permutation Graphs
- Permutation Graphs and Transitive Graphs
- A Characterization of Comparability Graphs and of Interval Graphs
