Max-Tolerance graphs as intersection graphs: Cliques, cycles and recognition

Abstract

We show that max-tolerance graphs are intersection graphs of congruent triangles in the plane, and we exploit this representation to show that their recognition is NP-hard, but one can find a maximum clique in polynomial time.

Keywords

• Max-Tolerance
• graphs
• intersection
• graphs
• Cliques
• cycles
• recognition