A New Intersection Model and Improved Algorithms for Tolerance Graphs

A New Intersection Model and Improved Algorithms for Tolerance Graphs George B. Mertzios1 Ignasi Sau2 Shmuel Zaks3 1RWTH Aachen University, Germany 2INRIA/CNRS/UNSA, Sophia-Antipolis, France UPC, Barcelona, Spain 3Technion, Haifa, Israel WG 2009 George Mertzios (RWTH Aachen Univ.) An Intersection Model for Tolerance Graphs WG 2009 1 / 26

• tolerance graphs


• sophia antipolis


• shmuel zaks3


• su ?


• mertzios1 ignasi


• minimum coloring


• intersection model


• lemma every


• open problems


• maximum clique