Two characterisations of minimal triangulations of 2K₂-free graphs

DOI10.1016/J.DISC.2006.07.001MaRDI QIDQ856888zbMATH OpenOpenAlexFDO

Authors 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

co-chordal graphslinear-time algorithmtreewidth

Mathematics Subject Classification ID

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

Recommendations

• A characterization of \(K_{2,4}\)-minor-free graphs
• Characterization of minimally (2,l)-connected graphs
• Two characterisations of the minimal triangulations of permutation graphs
• On triangles in \(K_r\)-minor free graphs
• scientific article; zbMATH DE number 4006304
• Basic maximal 2K₂-free graphs
• On Ramsey (2K₂, 2H)-minimal graphs
• On Ramsey \((2K_2, 2 P_n )\)-minimal graphs
• A characterization of the non-trivial diameter two graphs of minimum size
• scientific article; zbMATH DE number 1305094

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Finding and counting small induced subgraphs efficiently
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 1696538 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 861332 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• On diameters and radii of bridged graphs
• The Pathwidth and Treewidth of Cographs
• Triangulating graphs without asteroidal triples

Cited in

(13)

• On a property of minimal triangulations
• Nonempty intersection of longest paths in \(2K_2\)-free graphs
• Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs
• Upper bounds for the regularity of gap-free graphs in terms of minimal triangulation
• On regularity bounds and linear resolutions of toric algebras of graphs
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• Positive semidefinite zero forcing
• Characterization of 2-minimally nonouterplanar join graphs
• Two characterisations of the minimal triangulations of permutation graphs
• Treewidth-two graphs as a free algebra
• Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
• Existential closure in line graphs
• Edge contraction and forbidden induced subgraphs

This page was built for publication: Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs

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