The interval number of a planar graph is at most three
arXiv:1805.02947
The paper presents a new, shorter proof that any planar graph can be represented as the intersection graph of at most three intervals per vertex, confirming that the interval number of planar graphs is at most three.
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.
12 pages, 4 figures