pith. sign in

arxiv: 1805.02947 · v3 · pith:KXFLG3G2new · submitted 2018-05-08 · 🧮 math.CO · cs.DM

The interval number of a planar graph is at most three

classification 🧮 math.CO cs.DM
keywords graphintervalnumberintervalsplanarintersectionproofsets
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.