Book contents
- Frontmatter
- Contents
- Chapter Dependencies
- Preface
- 1 Introduction
- 2 Early work on tolerance graphs
- 3 Trees, cotrees and bipartite graphs
- 4 Interval probe graphs and sandwich problems
- 5 Bitolerance and the ordered sets perspective
- 6 Unit and 50% tolerance orders
- 7 Comparability invariance results
- 8 Recognition of bounded bitolerance orders and trapezoid graphs
- 9 Algorithms on tolerance graphs
- 10 The hierarchy of classes of bounded bitolerance orders
- 11 Tolerance models of paths and subtrees of a tree
- 12 φ-tolerance graphs
- 13 Directed tolerance graphs
- 14 Open questions and further directions of research
- References
- Index of Symbols
- Index
2 - Early work on tolerance graphs
Published online by Cambridge University Press: 11 August 2009
- Frontmatter
- Contents
- Chapter Dependencies
- Preface
- 1 Introduction
- 2 Early work on tolerance graphs
- 3 Trees, cotrees and bipartite graphs
- 4 Interval probe graphs and sandwich problems
- 5 Bitolerance and the ordered sets perspective
- 6 Unit and 50% tolerance orders
- 7 Comparability invariance results
- 8 Recognition of bounded bitolerance orders and trapezoid graphs
- 9 Algorithms on tolerance graphs
- 10 The hierarchy of classes of bounded bitolerance orders
- 11 Tolerance models of paths and subtrees of a tree
- 12 φ-tolerance graphs
- 13 Directed tolerance graphs
- 14 Open questions and further directions of research
- References
- Index of Symbols
- Index
Summary
In this chapter we discuss the definitions, results and open questions that appear in Golumbic and Monma (1982) and Golumbic, Monma, and Trotter (1984), the papers which introduced the topic of tolerance graphs. We also present consequences of these results and related topics from more recent literature.
Notation and observations
Recall from Section 1.3 that a graph G is a tolerance graph if each vertex ν ∈ V(G) can be assigned a closed interval Iν and a tolerance tν ∈ R+ so that xy ∈ E(G) if and only if |Ix ∩ Iy| ≥ min{tx, ty}. If graph G has a tolerance representation with tν ≤ |Iν| for all ν ∈ V(G), then G is called a bounded tolerance graph.
Many important graph properties are inherited by all induced subgraphs and thus called hereditary properties. Given a (bounded) tolerance representation 〈I, t〉 of a graph G, for any subset of vertices W ⊆ V(G) the intervals {Iw | w ∈ W} and tolerances {tw | w ∈ W} give a representation of GW. Thus, induced subgraphs of tolerance graphs are also tolerance graphs and induced subgraphs of bounded tolerance graphs are also bounded tolerance graphs. We record this as a remark.
Remark 2.1. The property of being a tolerance graph (resp. bounded tolerance graph) is hereditary.
In a tolerance representation of a graph G, we may have intervals of the form Ix = [ax, ax].
- Type
- Chapter
- Information
- Tolerance Graphs , pp. 29 - 52Publisher: Cambridge University PressPrint publication year: 2004