On the intersection of tolerance and cocomparability graphs

DOI10.1016/j.dam.2014.10.025zbMath1326.05097OpenAlexW1854376577MaRDI QIDQ896656

Shmuel Zaks, George B. Mertzios

Publication date: 10 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.10.025

zbMATH Keywords

tolerance graphstrapezoid graphscocomparability graphs3-dimensional intersection modelparallelogram graphs

Mathematics Subject Classification ID

Graph theory (05C99) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (1)

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A sufficient condition for boundedness of tolerance graphs
• On a problem concerning tolerance graphs
• Tolerance graphs
• Stability number and chromatic number of tolerance graphs
• A class of graphs each tolerance graph of which is a bounded one
• Efficient graph representations
• Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs
• Algorithmic graph theory and perfect graphs
• A note on tolerance graph recognition
• Proper and unit tolerance graphs
• Trapezoid order classification
• A characterization of triangle-free tolerance graphs
• A New Intersection Model and Improved Algorithms for Tolerance Graphs
• The Recognition of Tolerance and Bounded Tolerance Graphs
• Domination on Cocomparability Graphs
• Tolerance graphs, and orders
• Graph Classes: A Survey
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs

This page was built for publication: On the intersection of tolerance and cocomparability graphs