Bounds on lengths of intervals in bounded-degree interval graphs

Question

A graph is said to be an interval graph if its vertices can be associated with (closed) intervals on the real line $\mathbb R$ and there is an edge between two vertices if and only if the corresponding intervals intersect. An interval graph can have several different "interval representations". For example, given an interval representation of a graph, "scaling about a point" and/or "translating" gives another interval representation of the same graph. One can use the freedom to scale to ensure that the smallest interval is of length $1$. (One can also use the freedom to translate to ensure that the left most interval starts at the origin but this is not essential to my question below.)

Let $\mathcal G_\Delta$ be the class of all finite connected interval graphs of maximum degree $\Delta \ge 2$.

Question: For every graph in $\mathcal G_\Delta$, is there an interval representation where the lengths of all intervals are bounded between $1$ and some function of $\Delta$?

It is clear that the maximum length cannot be smaller than $\Delta-2$. This is because for a star graph where the central vertex has degree $\Delta$, the "tightest" interval representation would have $\Delta$ consecutive intervals of length $1$ (with some small separation between them so that they don't intersect). So the central vertex must correspond to an interval of size at least $\Delta-2$ so as to intersect all the other intervals.

---

I feel that the answer is yes because, intuitively, if an interval is too large, then it might potentially intersect more than $\Delta$ other intervals, or there might be "gaps" than can be "deleted". (The latter seems to suggest that this is some sort of a "packing" problem.) In fact, I think that the maximum length can be as small as $O(\Delta)$. However, I don't know how to make this intuition more precise. Any help is greatly appreciated.

---

Update: I asked a follow up and an extension of this question here.

Answer 1

Yes, we may take the function to be $2\Delta$.

Lemma. Every interval graph $G$ has an interval representation where all intervals have length between $1$ and $2\Delta$, where $\Delta$ is the maximum degree of $G$.

Proof. Let $G$ be an interval graph and choose a collection of intervals $\mathcal{I}$ that represents $G$, where the ends of each interval are distinct integers and the sum of the lengths of the intervals is as small as possible. Let $v$ be an arbitrary vertex of $G$ and suppose $v$ is represented by the interval $[a,b]$. Let $\ell_1, \dots, \ell_t$ be the left endpoints of the other intervals that intersect $[a,b]$ and $r_1, \dots, r_s$ be the right endpoints of the other intervals that intersect $[a,b]$. Since $G$ has maximum degree $\Delta$, we have that $\max\{s,t\} \leq \Delta$. We say that an integer $z \in [a,b]$ is contractible if $[z,z+1] \notin \mathcal{I}$ and there does not exist $i \in [s]$ and $j \in [t]$ such that $z=r_i$ and $z+1=\ell_j$. Note that if $z$ is contractible , then we can shorten $[a,b]$ by identifying $z$ and $z+1$ to obtain a set of intervals which still represents $G$. However, this contradicts the minimality of $\mathcal{I}$. On the other hand, if $[a,b]$ has length at least $2\Delta+1$, it is easy to see that at least one $z \in [a,b]$ is contractible. Therefore, $[a,b]$ has length at most $2\Delta$, as required.