The recognition of triangle graphs

DOI10.1016/J.TCS.2012.02.042zbMATH Open1246.05064OpenAlexW2151719453MaRDI QIDQ441856FDOQ441856

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)