The recognition of triangle graphs

DOI10.1016/j.tcs.2012.02.042zbMath1246.05064MaRDI 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 graphs; NP-complete; recognition problem; intersection graphs; \(PI^{\ast }\) graphs; PI graphs

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C17: Perfect graphs

Related Items

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

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