The interval number of a planar graph is at most three

05/08/2018
by   Guillaume Guégan, et al.
0

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. J. Comb. Theory, Ser. B, 35:224--239, 1983] proved that the interval number of any planar graph is at most 3. In this paper we present a flaw in the original proof and give another, different, and shorter proof of this result.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset