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
5 - Bitolerance and the ordered sets perspective
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
The concept of a bounded tolerance order
A set of real intervals {Iν | ν ∈ V} can be viewed as a representation of the interval graph G = (V, E) where xy ∈ E ⇔ Ix ∩ Iy ≠ Ø. It can also be interpreted as representing an interval order P = (V, ≺) where x ≺ y if and only if Ix is completely to the left of Iy (which we denote Ix ≪ Iy). The graph G and the order P are related in that G is the incomparability graph of P, that is, xy ∈ E(G) ⇔ x ∥ y in P. Thus, results about interval graphs have counterparts in the world of ordered sets. For example, note the similarity in the characterization theorems below.
Theorem 5.1.(Gilmore and Hoffman, 1964) A graph G is an interval graph if and only if it is a cocomparability graph with no induced C4.
Theorem 5.2.(Fishburn, 1970) An order P is an interval order if and only if it has no induced2 + 2.
The graph C4 is the incomparability graph of the order 2 + 2, so the same 4-element structure is forbidden in both theorems. Theorem 5.1 has the extra condition that G be a cocomparability graph. This is not needed in Theorem 5.2 since the relation in any ordered set is transitive, and thus the incomparability graph of any ordered set is always a cocomparability graph.
- Type
- Chapter
- Information
- Tolerance Graphs , pp. 84 - 97Publisher: Cambridge University PressPrint publication year: 2004