Towards a comprehensive theory of conflicttolerance graphs
Many graph classes are defined by the following paradigm: each vertex is assigned something measuring its size and something measuring its tolerance. If the combined sizes exceed the combined tolerances, then there is a conflict and the corresponding vertices are adjacent in a conflicttolerance graph. This paper attempts a broad formalization of the above notion. The goal is to provide a framework for classifying, comparing, and developing interesting models of graph representations.
graph representations intersection graphs interval graphs minimal forbidden subgraphs trees