The recognition of triangle graphs

DOI10.1016/J.TCS.2012.02.042MaRDI QIDQ441856zbMATH OpenOpenAlexFDO

Authors George B. Mertzios

Publication date 8 August 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.02.042

zbMATH Keywords

intersection graphsNP-completerecognition problemtrapezoid graphs\(PI^{\ast }\) graphsPI graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Perfect graphs (05C17) Network design and communication in computer systems (68M10)

Recommendations

• The recognition of triangle graphs
• scientific article; zbMATH DE number 1554936
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• On the structure of trapezoid graphs
• Vertex splitting and the recognition of trapezoid graphs

Cites work

• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• scientific article; zbMATH DE number 1554936 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• scientific article; zbMATH DE number 2197877 (Why is no real title available?)
• A recognition algorithm for orders of interval dimension two
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• Connected domination and dominating clique in trapezoid graphs
• Edge and vertex intersection of paths in a tree
• Efficient graph representations
• Graph Classes: A Survey
• Linear-Interval Dimension and PI Orders
• Modular decomposition and transitive orientation
• On the 2-Chain Subgraph Cover and Related Problems
• On the complexity of recognizing perfectly orderable graphs
• Proper and unit bitolerance orders and graphs
• Proper and unit tolerance graphs
• Split semiorders
• The complexity of comparability graph recognition and coloring
• The recognition of tolerance and bounded tolerance graphs
• Topics in Intersection Graph Theory
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring
• Trapezoid order classification
• Triangulating multitolerance graphs
• Vertex splitting and the recognition of trapezoid graphs

Cited in

(13)

• Algorithms and complexity of \(s\)-club cluster vertex deletion
• A recognition algorithm for simple-triangle graphs
• Extended Learning Graphs for Triangle Finding
• scientific article; zbMATH DE number 1554936 (Why is no real title available?)
• On the hardness of recognizing triangular line graphs
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• Recognition of triangles by covariogram
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• Hardness and algorithms for variants of line graphs of directed graphs
• Vertex splitting and the recognition of trapezoid graphs
• The recognition of triangle graphs
• Recognizing triangulated Cartesian graph products
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial

This page was built for publication: The recognition of triangle graphs

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