The Total Interval Number of a Graph II: Trees and Complexity
Thomas M. Kratzke, Douglas B. West · SIAM Journal on Discrete Mathematics · 1996
A multiple-interval representation of a simple graph G assigns each vertex a union of disjoint real intervals so 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 such a representation of G. For triangle-free graphs, $I(G) = | E(G) |+t(G)$, where $t(G)$ is the minimum number of pairwise edge-disjoint trails that together contain an endpoint of each edge. This yields the NP-completeness of testing $I(G) = | E(G) | + 1$ (even for triangle-free 3-regular planar graphs) and an alternative proof that HAMILTONIAN CYCLE is NP-complete for line graphs. It also yields a linear-time algorithm to compute $I(G)$ for trees and a characterization of the trees requiring $| E(G) | + t$ intervals for fixed t. Further corollaries include the Aigner-Andreae bound of $I(G) \leq \lfloor {(5n - 3)/4} \rfloor $ for n-vertex trees (achieved by subdividing every edge of a star), a characterization of the extremal trees, and a shorter proof of the extremal bound $\lfloor {(5m + 2)/4} \rfloor $ for connected graphs.