1. The interval number of a planar graph is at most three.
- Author
-
Guégan, Guillaume, Knauer, Kolja, Rollin, Jonathan, and Ueckerdt, Torsten
- Subjects
- *
PLANAR graphs , *INTERSECTION graph theory , *LABOR unions , *EVIDENCE - Abstract
The interval number of a graph G is the minimum k such that one can assign to each vertex of G a union of k intervals on the real line, such that G is the intersection graph of these sets, i.e., two vertices are adjacent in G if and only if the corresponding sets of intervals have non-empty intersection. Scheinerman and West (1983) [14] proved that the interval number of any planar graph is at most 3. However the original proof has a flaw. We give a different and shorter proof of this result. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF