Triangulating graphs with few P₄'s

DOI10.1016/S0166-218X(98)00115-2MaRDI QIDQ1281383zbMATH OpenFDO

Authors Luitpold Babel

Publication date 29 November 1999

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(98)00115-2

zbMATH Keywords

cographstriangulation

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Treewidth and minimum fill-in on permutation graphs in linear time
• scientific article; zbMATH DE number 1304320
• scientific article; zbMATH DE number 1305094
• How to use the minimal separators of a graph for its chordal triangulation
• Minimal triangulations of graphs: a survey

Cites work

• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Linear Recognition Algorithm for Cographs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Complement reducible graphs
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Hamiltonicity in graphs with few \(P_ 4\)'s
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 1262809 (Why is no real title available?)
• scientific article; zbMATH DE number 2102752 (Why is no real title available?)
• scientific article; zbMATH DE number 6472575 (Why is no real title available?)
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• On extended P₄-reducible and extended P₄-sparse graphs
• On the structure of graphs with few P₄s
• P-Components and the Homogeneous Decomposition of Graphs
• The Pathwidth and Treewidth of Cographs
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Treewidth. Computations and approximations
• Triangulating graphs without asteroidal triples

Cited in

(7)

• Akempic triangulations with 4 odd vertices
• On triangulating planar graphs under the four-connectivity constraint
• On hypergraphs with every four points spanning at most two triples
• The graph of triangulations of a point configuration with \(d+4\) vertices is 3-connected
• Recognition and isomorphism of tree-like \(P_4\)-connected graphs
• The maker-breaker largest connected subgraph game
• scientific article; zbMATH DE number 3891400 (Why is no real title available?)

This page was built for publication: Triangulating graphs with few \(P_4\)'s

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1281383)