Publication
Discrete Applied Mathematics
Paper

Tolerance graphs

View publication

Abstract

Tolerance graphs arise from the intersection of intervals with varying tolerances in a way that generalizes both interval graphs and permutation graphs. In this paper we prove that every tolerance graph is perfect by demonstrating that its complement is perfectly orderable. We show that a tolerance graph cannot contain a chordless cycle of length greater than or equal to 5 nor the complement of one. We also discuss the subclasses of bounded tolerance graphs, proper tolerance graphs, and unit tolerance graphs and present several possible applications and open questions. © 1984.

Date

01 Jan 1984

Publication

Discrete Applied Mathematics

Share