The interval number of a graph G, denoted i(G), is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investigate the maximum value of the interval number for graphs with higher genus and show that the maximum value of the interval number of graphs with genus g is between and 3 + r-1.
We also show that the maximum arboricity of graphs with genus g is either 1 +
1. Introduction
A r-inrerval is a subset of the real line that is the union of (at most) t compact intervals. A t-interval graph is an intersection graph of t-intervals. Thus a (simple, finite) graph G is a r-interval graph if and only if to each vertex of G there is an assignment of t-intervals so that u is adjacent to w if and only if some interval assigned to LJ intersects some interval assigned to w. The interval number of a graph G , denoted i ( G ) , is the least positive integer t so that G is a t-interval graph. Some interesting applications of the multiple interval graphs and the interval number can be found in 171.
In [7] it was shown that if G is a planar graph, then i ( G ) d 3, and that this result is best possible. If G is nonplanar, then it can be readily shown that G may have unbounded interval number (see Lemma 1 below). Instead, we choose to investigate interval number in connection to a graph's genus. The genus of a graph G , denoted y ( G ) , is the least positive integer g so that G has a topological embedding on a surface with genus g. Complete graphs have arbi-