The total interval number of a graph

AbstractA representation f of a graph G is a mapping f which assigns to each vertex of G a non-empty collection of intervals on the real line so that two distinct vertices x and y are adjacent if and only if there are intervals I ∈ f(x) and J ∈ f(y) with I ⌢ J ≠ ∅. We study the total interval number of G, defined as I(G) = min{Σx ∈ V(G) |f(x)|: f is a representation of G}. Let n be the number of vertices of G. Our main results on I(G) are: (a) If G is a tree then I(G) ≤ ⌊5n4 − 34⌋ for (c) If G is a triangle-free planar graph then I(G) ≤ 2n − 3 for n ≥ 3. (d) If G is any triangle-free graph then I(G) ≤ ⌊n2⌋ ⌊n2⌋ + 1. All bounds are sharp and for n ≥ 4 the bound of (d) is achieved iff G = K⌊n2⌋,⌊n2⌋. We conjecture that results (b)-(d) remain valid without the hypothesis “triangle-free” and present some partial results on this conjecture. We close with a result on the related concept of the depth-two total interval number and some open problems