Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs

DOI10.1016/j.disc.2006.07.001zbMath1105.05067OpenAlexW2050505659MaRDI QIDQ856888

Daniel Meister

Publication date: 14 December 2006

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

Full work available at URL: https://doi.org/10.1016/j.disc.2006.07.001

zbMATH Keywords

treewidthlinear-time algorithmco-chordal graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Nonempty intersection of longest paths in \(2K_2\)-free graphs, On regularity bounds and linear resolutions of toric algebras of graphs, Two characterisations of the minimal triangulations of permutation graphs, Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs, Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs, Positive semidefinite zero forcing, Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs, On a property of minimal triangulations, Upper bounds for the regularity of gap-free graphs in terms of minimal triangulation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting small induced subgraphs efficiently
• Matrix multiplication via arithmetic progressions
• On diameters and radii of bridged graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Triangulating graphs without asteroidal triples
• Graph minors. II. Algorithmic aspects of tree-width
• Algorithmic Aspects of Vertex Elimination on Graphs
• The Pathwidth and Treewidth of Cographs