1. The interval number of a planar graph is at most three
- Author
-
Guégan, Guillaume, Knauer, Kolja, Rollin, Jonathan, Ueckerdt, Torsten, Guégan, Guillaume, Knauer, Kolja, Rollin, Jonathan, and Ueckerdt, Torsten
- 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. In 1983 Scheinerman and West [The interval number of a planar graph: Three intervals suffice. \textit{J.~Comb.~Theory, Ser.~B}, 35:224--239, 1983] 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., Comment: 12 pages, 4 figures
- Published
- 2018