The total interval number of a graph, I: Fundamental classes

AbstractA multiple-interval representation of a simple graph G assigns each vertex a union of disjoint real intervals, such that vertices are adjacent if and only if their assigned sets intersect. The total interval number I(G) is the minimum of the total number of intervals used in any such representation of G. We obtain the maximum value of I(G) for n-vertex graphs (⌈(n2+1)4⌉), n-vertex outerplanar graphs (⌊3n2−1⌋), and m-edge connected graphs (⌊(5m+2)4⌋)