The recognition of triangle graphs

DOI10.1016/j.tcs.2012.02.042zbMath1246.05064OpenAlexW2151719453MaRDI QIDQ441856

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

trapezoid graphsNP-completerecognition problemintersection graphs\(PI^{\ast }\) graphsPI graphs

Mathematics Subject Classification ID

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

Related Items (5)

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ A recognition algorithm for simple-triangle graphs ⋮ The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trapezoid graphs and generalizations, geometry and algorithms
• On the complexity of recognizing perfectly orderable graphs
• Edge and vertex intersection of paths in a tree
• Trapezoid graphs and their coloring
• The complexity of comparability graph recognition and coloring
• Split semiorders
• Modular decomposition and transitive orientation
• Proper and unit bitolerance orders and graphs
• Triangulating multitolerance graphs
• Efficient graph representations
• 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
• The Recognition of Tolerance and Bounded Tolerance Graphs
• Linear-Interval Dimension and PI Orders
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• On the 2-Chain Subgraph Cover and Related Problems

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