A Characterization of Mixed Unit Interval Graphs

Abstract

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half-open unit intervals of the real line. This is a proper superclass of the well known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach and Szwarcfiter (Mixed unit interval graphs. Discrete Math. 312, 3357–3363 (2012)). Our characterization also leads to a polynomial-time recognition algorithm for mixed unit interval graphs.

1 Introduction

A graph $G$ is an interval graph, if there is a function $I$ from the vertex set of $G$ to the set of intervals of the real line such that two vertices are adjacent if and only if their assigned intervals intersect. The function $I$ is an interval representation of $G$. Interval graphs are well known and investigated – algorithmically as well as structurally [4, 6, 9]. There are several efficient algorithms that decide, if a given graph is an interval graph. See for example [2].

An important subclass of interval graphs are unit interval graphs. An interval graph $G$ is a unit interval graph, if there is an interval representation $I$ of $G$ such that $I$ assigns to every vertex a closed interval of unit length. This subclass is well understood and also easy to characterize structurally [11] as well as algorithmically [1].

Frankl and Maehara [5] showed that it does not matter, if we assign the vertices of $G$ only to closed intervals or only to open intervals of unit length. Rautenbach and Szwarcfiter [10] characterized, by a finite list of forbidden induced subgraphs, all interval graphs $G$ such that there is an interval representation of $G$ that uses only open and closed unit intervals.

Dourado et al. [3] gave a characterization of all diamond-free interval graphs that have an interval representation such that all vertices are assigned to unit intervals, where all kinds of unit intervals are allowed and a diamond is a complete graph on four vertices minus an edge. Furthermore, they made a conjecture concerning the general case.

We prove that their conjecture is not completely correct and give a complete characterization of this class. Since the conjecture is rather technical and not given by a list of forbidden subgraphs, we refer the reader to [3] for a detailed formulation of the conjecture, but roughly speaking, they missed the class of forbidden subgraphs shown in Fig. 6. Moreover, we provide a polynomial-time recognition algorithm for this graph class.

In Sect. 2 we introduce all definitions and relate our results to other work. In Sect. 3 we state and prove our results.

2 Preliminary Remarks

We only consider finite, undirected, and simple graphs. Let $G$ be a graph. We denote by $V(G)$ and $E(G)$ the vertex and edge set of $G$, respectively. If $C$ is a set of vertices, then we denote by $G[C]$ the subgraph of $G$ induced by $C$. Let $\mathcal {M}$ be a set of graphs. We say $G$ is $\mathcal {M}$-free, if for every $H\in \mathcal {M}$, the graph $H$ is not an induced subgraph of $G$. For a vertex $v\in V(G)$, let the neighborhood $N_G(v)$ of $v$ be the set of all vertices that are adjacent to $v$ and let the closed neighborhood $N_G[v]$ be defined by $N_G(v)\cup \{v\}$. Two distinct vertices $u$ and $v$ are twins (in $G$) if $N_G[u]=N_G[v]$. If $G$ contains no twins, then $G$ is twin-free.

Let $\mathcal {N}$ be a family of sets. We say a graph $G$ has an $\mathcal {N}$-intersection representation, if there is a function $f:V(G)\rightarrow \mathcal {N}$ such that for any two distinct vertices $u$ and $v$, there is an edge joining $u$ and $v$ if and only if $f(u)\cap f(v)\not =\emptyset$. If there is an $\mathcal {N}$-intersection representation for $G$, then $G$ is an $\mathcal {N}$-graph. Let $x,y\in \mathbb {R}$. We denote by

$$ [x,y]=\{z\in \mathbb {R}: x\le z\le y\} $$

the closed interval, by

$$ (x,y)=\{z\in \mathbb {R}: x< z<y\} $$

the open interval, by

$$ (x,y]=\{z\in \mathbb {R}: x< z\le y\} $$

the open-closed interval, and by

$$ [x,y)=\{z\in \mathbb {R}: x\le z< y\} $$

the closed-open interval of $x$ and $y$. For an interval $A$, let $\ell (A)=\inf \{x\in \mathbb {R}:x\in A\}$ and $r(A)=\sup \{x\in \mathbb {R}:x\in A\}$. If $I$ is an interval representation of $G$ and $v\in V(G)$, then we write $\ell (v)$ and $r(v)$ instead of $\ell (I(v))$ and $r(I(v))$, respectively, if there are no ambiguities. Let $\mathcal {I}^{++}$ be the set of all closed intervals, $\mathcal {I}^{--}$ be the set of all open intervals, $\mathcal {I}^{-+}$ be the set of all open-closed intervals, $\mathcal {I}^{+-}$ be the set of all closed-open intervals, and $\mathcal {I}$ be the set of all intervals. In addition, let $\mathcal {U}^{++}$ be the set of all closed unit intervals, $\mathcal {U}^{--}$ be the set of all open unit intervals, $\mathcal {U}^{-+}$ be the set of all open-closed unit intervals, $\mathcal {U}^{+-}$ be the set of all closed-open unit intervals, and $\mathcal {U}$ be the set of all unit intervals. We call a $\mathcal {U}$-graph a mixed unit interval graph.

By a result of [3, 10], every interval graph is an $\mathcal {I}^{++}$-graph. With our notation unit interval graphs equals $\mathcal {U}^{++}$-graphs. An interval graph $G$ is a proper interval graph if there is an interval representation of $G$ such that $I(u)\not \subseteq I(v)$ for every distinct $u,v\in V(G)$.

The next result due to Roberts characterizes unit interval graphs.

Theorem 1

(Roberts [11]). The classes of unit interval graphs, proper interval graphs, and $K_{1,3}$-free interval graphs are the same.

The second result shows that several natural subclasses of mixed unit interval graphs actually coincide with the class of unit interval graphs.

Theorem 2

(Dourado et al., Frankl and Maehara [3, 5]). The classes of $\mathcal {U}^{++}$-graphs, $\mathcal {U}^{--}$-graphs, $\mathcal {U}^{+-}$-graphs, $\mathcal {U}^{-+}$-graphs, and $\mathcal {U}^{+-} \cup \mathcal {U}^{-+}$-graphs are the same.

A graph $G$ is a mixed proper interval graph (respectively an almost proper interval graph) if $G$ has an interval representation $I:V(G)\rightarrow \mathcal {I}$ (respectively $I:V(G)\rightarrow \mathcal {I}^{++}\cup \mathcal {I}^{--}$) such that

• there are no two distinct vertices $u$ and $v$ of $G$ with $I(u),I(v)\in \mathcal {I}^{++}$, $I(u)\subseteq I(v)$, and $I(u)\not =I(v)$, and

• for every vertex $u$ of $G$ with $I(u)\notin \mathcal {I}^{++}$, there is a vertex $v$ of $G$ with $I(v)\in \mathcal {I}^{++}$, $\ell (u)=\ell (v)$, and $r(u)=r(v)$.

A natural class extending the class of unit interval graphs are $\mathcal {U}^{++} \cup \mathcal {U}^{--}$-graphs. These were characterized by Rautenbach and Szwarcfiter.

Fig. 1.

Forbidden induced subgraphs for twin-free $\mathcal {U}^{++}\cup \mathcal {U}^{--}$-graphs.

Theorem 3

(Rautenbach and Szwarcfiter [10]). For a twin-free interval graph $G$, the following statements are equivalent.

• $G$ is a $\{K_{1,4},K_{1,4}^*,K_{2,3}^*,K_{2,4}^*\}$-free graph. (See Fig. 1 for an illustration.)

• $G$ is an almost proper interval graph.

• $G$ is a $\mathcal {U}^{++}\cup \mathcal {U}^{--}$-graph.

Note that an interval representation can assign the same interval to twins and hence the restriction to twin-free graphs does not weaken the statement but simplifies the description.

The next step is to allow all different types of unit intervals. The class of $\mathcal {U}$-graphs is a proper superclass of the $\mathcal {U}^{++}\cup \mathcal {U}^{--}$-graphs, because the graph illustrated in Fig. 2 is a $\mathcal {U}$-graph, but not a $\mathcal {U}^{++}\cup \mathcal {U}^{--}$-graph (it contains a $K_{1,4}^*$). Dourado et al. already made some progress in characterizing this class.

Fig. 2.

A graph, which is a $\mathcal {U}$-graph, but not a $\mathcal {U}^{++}\cup \mathcal {U}^{--}$-graph.

Theorem 4

(Dourado et al. [3]). For a graph $G$, the following two statements are equivalent.

• $G$ is a mixed proper interval graph.

• $G$ is a mixed unit interval graph.

They also characterized diamond-free mixed unit interval graphs. There is another approach by Le and Rautenbach [8] to understand the class of $\mathcal {U}$-graphs by restricting the ends of the unit intervals to integers. They found a infinite list of forbidden induced subgraphs, which characterize these so-called integral $\mathcal {U}$-graphs.

3 Results

In this section we state and prove our main results. We start by introducing a list of forbidden induced subgraphs. See Figs. 3, 4, 5, and 6 for illustration. Let $\mathcal {R}=\bigcup _{i=0}^{\infty }\{R_i\}$, $\mathcal {S}=\bigcup _{i=1}^{\infty }\{S_i\}$, $\mathcal {S'}= \bigcup _{i=1}^{\infty }\{S_i'\}$, and $\mathcal {T}=\bigcup _{i\ge j\ge 0}\{T_{i,j}\}$. For $k\in \mathbb {N}$ let the graph $Q_k$ arise from the graph $R_k$ by deleting two vertices of degree one, which have a common neighbor. We call the common neighbor of the two deleted vertices and its neighbor of degree two special vertices of $Q_k$. Note that if a graph $G$ is twin-free, then the interval representation of $G$ is injective.

Fig. 3.

The class $\mathcal {R}$.

Fig. 4.

The class $\mathcal {S}$.

Fig. 5.

The class $\mathcal {S}'$.

Lemma 5

(Dourado et al. [3]). Let $k\in \mathbb {N}$.

• (a) Every $\mathcal {U}$-representation of the claw $K_{1,3}$ arises by translation of the following $\mathcal {U}$-representation $I: V(K_{1,3})\rightarrow \mathcal {U}$ of $K_{1,3}$, where $I(V(K_{1,3}))$ consists of the following intervals

  • either $[0,1]$ or $(0,1]$,

  • $[1,2]$ and $(1,2)$, and

  • either $[2,3]$ or $[2,3)$.

• (b) Every injective $\mathcal {U}$-representation of $Q_k$ arises by translation and inversion of one of the two injective $\mathcal {U}$-representations $I: V(Q_k)\rightarrow \mathcal {U}$ of $Q_k$, where $I(V(Q_k))$ consists of the following intervals

  • either $[0,1]$ or $(0,1]$,

  • $[1,2]$ and $(1,2)$, and

  • $[i,i+1]$ and $[i,i+1)$ for $2\le i \le k+1$.

• (c) The graphs in $\{T_{0,0}\}\cup \mathcal {R}$ are minimal forbidden subgraphs for the class of $\mathcal {U}$-graphs with respect to induced subgraphs.

• (d) If $G$ is a $\mathcal {U}$-graph, then every induced subgraph $H$ in $G$ that is isomorphic to $Q_k$ and every vertex $u^*\in V(G)\setminus V(H)$ such that $u^*$ is adjacent to exactly one of the two special vertices of $H$, the vertex $u^*$ has exactly one neighbor in $V(H)$.

Lemma 6

If a graph $G$ is a twin-free mixed unit interval graph, then $G$ is $\{K_{2,3}^*\}\cup \mathcal {R}\cup \mathcal {S}\cup \mathcal {S'}\cup \mathcal {T}$-free.

For the sake of space restrictions, we omit the proof of Lemma 6 and proceed to our main result.

Theorem 7

A twin-free graph $G$ is a mixed unit interval graph if and only if $G$ is a $\{K_{2,3}^*\}\cup \mathcal {R}\cup \mathcal {S}\cup \mathcal {S'}\cup \mathcal {T}$-free interval graph.

Fig. 6.

The class $\mathcal {T}$.

Proof of Theorem 7: By Lemma 6, we know if $G$ is a twin-free mixed unit interval graph, then $G$ is a $\{K_{2,3}^*\}\cup \mathcal {R}\cup \mathcal {S}\cup \mathcal {S'}\cup \mathcal {T}$-free interval graph. Let now $G$ be a twin-free $\{K_{2,3}^*\}\cup \mathcal {R}\cup \mathcal {S}\cup \mathcal {S'}\cup \mathcal {T}$-free interval graph. We show that $G$ is a mixed proper interval graph. By Theorem 4, this proves Theorem 7. Since $G$ is an interval graph, $G$ has an $\mathcal {I}^{++}$-representation $I$. As in [10] we call a pair $(u,v)$ of distinct vertices a bad pair if $I(u)\subseteq I(v)$. Let $I$ be such that the number of bad pairs is as small as possible. If $I$ has no bad pair, then we are done by Theorem 1. Hence we assume that there is at least one bad pair. The strategy of the proof is as follows. Claims 1 to 6 collect properties of $G$ and $I$, before we modify our interval representation of $G$ to show that $G$ is a mixed proper interval graph. In Claims 7 to 10 we prove that our modification of the interval representation preserves all intersections and non-intersections. Claims 1 to 3 are similar to Claims 1 to 3 in [10], respectively. For the sake of space restrictions we omit the proofs.

Claim 1

If $(u,v)$ is a bad pair, then there are vertices $x$ and $y$ such that $\ell (v)\le r(x)< \ell (u)$ and $r(u)<\ell (y)\le r(v)$.

Let $a_1$ and $a_2$ be two distinct vertices. Claim 1 implies that $\ell (a_1)\not =\ell (a_2)$ and $r(a_1)\not =r(a_2)$. Suppose $\ell (a_1)<\ell (a_2)$. Let $\epsilon$ be the smallest distance between two distinct endpoints of intervals of $I$. If $r(a_1)=\ell (a_2)$, then $I': V(G)\rightarrow \mathcal {I}^{++}$ be such that $I'(a_1)=[\ell (a_1),r(a_1)+\epsilon /2]$, and $I'(z)=I(z)$ for $z\in V(G)\setminus \{a_1\}$. By the choice of $\epsilon$, we conclude that $I'$ is an interval representation of $G$ with as many bad pairs as $I$. Therefore, we assume without loss of generality that we chose $I$ such that all endpoints of the intervals of $I$ are distinct. Hence the inequalities in Claim 1 are strict inequalities.

Claim 2

If $(u,w)$ and $(v,w)$ are bad pairs, then $u=v$, that is, no interval contains two distinct intervals.

Claim 3

If $(u,v)$ and $(u,w)$ are bad pairs, then $v=w$, that is, no interval is contained in two distinct intervals.

A vertex $x$ is to the left (respectively right) of a vertex $y$ (in $I$), if $r(x)<\ell (y)$ (respectively $r(y)<\ell (x)$). Two adjacent vertices $x$ and $y$ are distinguishable by vertices to the left (respectively right) of them, if there is a vertex $z$, which is adjacent to exactly one of them and to the left (respectively right) of one of them. The vertex $z$ distinguishes $x$ and $y$. Next, we show that for a bad pair $(u,v)$ there is the structure as shown in Fig. 7 in $G$. We introduce a positive integer $\ell _{u,v}^\mathrm{max}$ that, roughly speaking, indicates how large this structure is.

Fig. 7.

The structure in $G$ forced by a bad pair $(u,v)$.

For a bad pair $(u,v)$ let $v=X_{u,v}^0$ and let $X_{u,v}^1$ be the set of vertices that are adjacent to $v$ and to the left of $u$. Let $y_{u,v}$ be a vertex to the right of $u$ and adjacent to $v$. Claim 1 guarantees $|X_{u,v}^1|\ge 1$ and the existence of $y_{u,v}$. If $|X_{u,v}^1|=1$, then let $\ell _{u,v}^\mathrm{max}=1$ and we stop here. Suppose $|X_{u,v}^1|\ge 2$. Since $G$ is $R_0$-free, $X_{u,v}^1$ is a clique and since $G$ is $S_1'$-free, we conclude $|X_{u,v}^1|=2$. Let $\{x,x'\}= X_{u,v}^1$ such that $r(x)< r(x')$. For contradiction, we assume that there is a vertex $z$ to the right of $x$ that distinguishes $x$ and $x'$. We conclude $\ell (v)<\ell (z)$. By Claim 2, $r(v)< r(z)$. This implies that $(u,z)$ is a bad pair, which contradicts Claim 3. Thus $z$ does not exist. In addition $(x,x')$ is not a bad pair, otherwise Claim 1 guarantees a vertex $z$ such that $r(x)<\ell (z)<r(x')$, which is a contradiction. Thus $\ell (x)<\ell (x')<r(x)< r(x')$. Let $x_{u,v}^1=x$ and ${x_{u,v}^1}'=x'$. Note that $N_G({x^1_{u,v}}')\subset N_G(x^1_{u,v})$.

Let $X_{u,v}^2=N_G(x^1_{u,v})\setminus N_G({x^1_{u,v}}')$. Note that all vertices in $X_{u,v}^2$ are to the left of ${x^1_{u,v}}'$. Since $G$ is twin-free, $|X_{u,v}^2|\ge 1$. If $|X_{u,v}^2|=1$, then let $\ell _{u,v}^\mathrm{max}=2$ and we stop here. Suppose $|X_{u,v}^2|\ge 2$. Since $G$ is $R_1$-free, $X_{u,v}^2$ is a clique and since $G$ is $S_2'$-free, we conclude $|X_{u,v}^2|=2$. Let $\{x,x'\}= X_{u,v}^2$ such that $r(x)< r(x')$. For contradiction, we assume that there is a vertex $z$ to the right of $x$ that distinguishes $x$ and $x'$. Since $z\notin X_{u,v}^2$, we conclude $\ell ({x_{u,v}^1}')< r(z)$. If $r(z)<\ell (v)$, then $G[\{z,x,x',{x_{u,v}^1},{x_{u,v}^1}',v,u,y_{u,v}\}]$ is isomorphic to $S_2$, which is a contradiction. Thus $\ell (v)< r(z)$. If $r(z)< \ell (u)$, then $|X_{u,v}^1|=3$, which is a contradiction. Thus $\ell (u)< r(z)$. If $r(u)< r(z)$, then $(u,v)$ and $(u,z)$ are bad pairs, which is a contradiction to Claim 3. Thus $\ell (u)< r(z)<r(u)$. Now $G[\{z,x',{x_{u,v}^1}',v,u,y_{u,v}\}]$ is isomorphic to $T_{0,0}$, which is the final contradiction.

Note that $(x,x')$ is not a bad pair, otherwise Claim 1 guarantees a vertex $z$ such that $r(x)<\ell (z)< r(x')$, which is a contradiction. Thus $\ell (x)<\ell (x')<r(x)< r(x')$. Let $x_{u,v}^2=x$ and ${x_{u,v}^2}'=x'$. Note that $N_G({x^2_{u,v}}')\subset N_G(x^2_{u,v})$. Let $X_{u,v}^3=N_G(x^2_{u,v})\setminus N_G({x^2_{u,v}}')$. Note that all vertices in $X_{u,v}^3$ are to the left of ${x^2_{u,v}}'$.

We assume that for $k\ge 3$, $i\in [k-1]$ and $j\in [k]$

• we defined $X_{u,v}^j$,

• $|X_{u,v}^i|=2$ holds,

• we defined $x_{u,v}^i$ and ${x_{u,v}^i}'$,

• $\ell (x_{u,v}^i)<\ell ({x_{u,v}^i}')<r(x_{u,v}^i)<r({x_{u,v}^i}')$ holds,

• the vertices in $X_{u,v}^{i+1}$ are to the left of ${x^{i}_{u,v}}'$, and

• the vertices in $X_{u,v}^i$ are not distinguishable to the right.

If $|X_{u,v}^k|=1$, then let $\ell _{u,v}^\mathrm{max}=k$ and we stop here. Suppose $|X_{u,v}^k|\ge 2$. Since $G$ is $R_{k-1}$-free, $X_{u,v}^k$ is a clique and since $G$ is $S_k'$-free, we obtain $|X_{u,v}^k|=2$. Let $\{x,x'\}= X_{u,v}^k$ such that $r(x)< r(x')$. For contradiction, we assume that there is a vertex $z$ to the right of $x$ that distinguishes $x$ and $x'$. Since $z\notin X_{u,v}^k$, we conclude $\ell ({x_{u,v}^{k-1}}')< r(z)$. If $r(z)<\ell (x_{u,v}^{k-2})$, then $G[\{z,x,x',v,u,y_{u,v}\}\cup \bigcup _{i=1}^{k-1}X_{u,v}^i]$ is isomorphic to $S_k$, which is a contradiction. Thus $\ell (x_{u,v}^{k-2})< r(z)$. If $r(z)<\ell ({x_{u,v}^{k-2}}')$, then $|X_{u,v}^{k-1}|=3$, which is a contradiction. Thus $\ell ({x_{u,v}^{k-2}}')< r(z)$. If $r(z)<\ell (x_{u,v}^{k-3})$, then $G[\{z,x',{x_{u,v}^{k-1}}',v,u,y_{u,v}\}\cup \bigcup _{i=1}^{k-2}X_{u,v}^i]$ is isomorphic to $T_{k-3,0}$, which is a contradiction. Thus $\ell (x_{u,v}^{k-3})< r(z)$. If $r(z)< r(x_{u,v}^{k-2})$, then $|X_{u,v}^{k-2}|=3$, which is a contradiction. Thus $r(x_{u,v}^{k-2})<r(z)$ and hence $({x_{u,v}^{k-1}}',z)$ and $(x_{u,v}^{k-2},z)$ are bad pairs, which is a contradiction to Claim 2. Thus $x,x'$ are not distinguishable to the right. We obtain that $(x,x')$ is not a bad pair, otherwise Claim 1 guarantees a vertex $z$ such that $r(x)<\ell (z)< r(x')$, which is a contradiction. Thus $\ell (x)<\ell (x')<r(x)< r(x')$. Let $x_{u,v}^k=x$ and ${x_{u,v}^k}'=x'$. Note that $N_G({x^k_{u,v}}')\subset N_G(x^k_{u,v})$. Let $X_{u,v}^{k+1}=N_G(x^k_{u,v})\setminus N_G({x^k_{u,v}}')$. Note that all vertices in $X_{u,v}^{k+1}$ are to the left of ${x^k_{u,v}}'$. By induction, this leads to the following properties.

Claim 4

If $(u,v)$ is a bad pair, $k\in [\ell _{u,v}^\mathrm{max}-1]$, then the following holds:

• (a) $|X_{u,v}^k|= 2$.

• (b) The vertices in $X_{u,v}^k$ are not distinguishable by vertices to the right of them.

• (c) We have $\ell (x_{u,v}^i)<\ell ({x_{u,v}^i}')<r(x_{u,v}^i)<r({x_{u,v}^i}')$, that is $(x^k_{u,v},{x^k_{u,v}}')$ and $({x^k_{u,v}}',x^k_{u,v})$ are not bad pairs.

Note that $\ell _{u,v}^\mathrm{max}$ is the smallest integer $k$ such that $|X_{u,v}^{k-1}|\ge 2$ and $|X_{u,v}^{k}|=1$. Due to space restrictions, we omit the proofs of Claims 5 and 6.

Claim 5

If $(u,v)$ is a bad pair and $k\in [\ell _{u,v}^\mathrm{max}-1]$, then the following holds.

• (a) ${x_{u,v}^k}'$ is not contained in a bad pair.

• (b) There is no vertex $z\in V(G)$ such that $(x_{u,v}^k,z)$ is a bad pair.

For a bad pair $(u,v)$ define $Y_{u,v}^k$ as $X_{u,v}^k$ by interchanging in the definition right by left. Let $r_{u,v}^\mathrm{max}$ be the smallest integer $k$ such that $|Y_{u,v}^{k-1}|= 2$ and $|Y_{u,v}^{k}|= 1$. By symmetry, one can prove a “y”-version of Claims 4, 5 and 6(a) and (b). Let $\{y_{u,v}^k,{y_{u,v}^k}'\}=Y_{u,v}^k$ such that $N_G({y^k_{u,v}}')\subset N_G(y^k_{u,v})$ for $k\le r_{u,v}^\mathrm{max}-1$.

Claim 6

Let $(u,v)$ and $(w,z)$ be bad pairs and $k\in [\ell _{u,v}^\mathrm{max}]$.

• (a) If $X_{u,v}^{k}\cap X_{w,z}^{\tilde{k}}\not =\emptyset$, then $x_{u,v}^{k-1}=x_{w,z}^{\tilde{k}-1}$ for $\tilde{k}\in [\ell _{w,z}^\mathrm{max}]$.

• (b) If $X_{u,v}^{k}\cap X_{w,z}^{\tilde{k}}\not =\emptyset$, then $X_{u,v}^{k}=X_{w,z}^{\tilde{k}}$ for $\tilde{k}\in [\ell _{w,z}^\mathrm{max}]$.

• (c) If $X_{u,v}^{k}\cap Y_{w,z}^{\tilde{k}}\not =\emptyset$, then $X_{u,v}^{k}\cap Y_{w,z}^{\tilde{k}}=x_{u,v}^{k}= y_{w,z}^{\tilde{k}}$ for $\tilde{k}\in [r_{w,z}^\mathrm{max}]$

Next, we define step by step new interval representations of $G$ as follows. First we shorten the intervals of $X_{u,v}^{k}$ for every bad pair $(u,v)$ and $k\in [\ell _{u,v}^\mathrm{max}]$. Let $I':V(G)\rightarrow \mathcal {I}^{++}$ be such that $I'(x)=[\ell (x),\ell (x_{u,v}^{k-1})]$ if $x\in X_{u,v}^k$ for some bad pair $(u,v)$ and $I'(x)=I(x)$ otherwise. By Claim 6(a), $I'$ is well-defined; that is, if $x\in X_{u,v}^k\cap X_{w,z}^{\tilde{k}}$, then $\ell (x_{u,v}^{k-1})=\ell (x_{w,z}^{\tilde{k}-1})$. Let $\ell '(x)$ and $r'(x)$ be the left and right endpoint of the interval $I'(x)$ for $x\in V(G)$, respectively.

Claim 7

$I'$ is an interval representation of $G$.

Proof of Claim 7: Trivially, if two intervals do not intersect in $I$, then they do not intersect in $I'$. For contradiction, we assume that there are two vertices $a,b\in V(G)$ such that $I(a)\cap I(b)\not = \emptyset$ and $I'(a)\cap I'(b)= \emptyset$. At least one interval is shorten by changing the interval representation. Say $a\in X_{u,v}^k$ for some bad pair $(u,v)$ and $k\in [\ell _{u,v}^\mathrm{max}]$. Hence $b\not =x_{u,v}^{k-1}$ and $\ell (x_{u,v}^{k-1})<\ell (b)$ and by Claim 4(b), $\ell (b)< r({x_{u,v}^{k}})$. We conclude that $(b,x_{u,v}^{k-1})$ is not a bad pair, otherwise Claim 1 implies the existence of a vertex $z\in X_{u,v}^{k}$ to the left of $b$, but $z\notin \{x_{u,v}^{k},{x_{u,v}^{k}}'\}$, which is a contradiction to Claim 4(a). Thus $r(x_{u,v}^{k-1})<r(b)$. If $k=1$, then $(u,b)$ is also a bad pair, which is a contradiction to Claim 3. Thus $k\ge 2$. Since $\ell (b)< r({x_{u,v}^{k}})$, we obtain $\ell (b)<\ell ({x_{u,v}^{k-1}}')$. Since $({x_{u,v}^{k-1}}',b)$ is not a bad pair by Claim 5(a), $r(b)<r({x_{u,v}^{k-1}}')$. Thus $b\in X_{u,v}^{k-1}$, which is a contradiction to $|X_{u,v}^{k-1}|=2$.   $\Box$

Claim 8

The change of the interval representation of $G$ from $I$ to $I'$ creates no new bad pair $(a,b)$ such that $\{a,b\}\not = X_{u,v}^k$ for some $k\in [\ell _{u,v}^\mathrm{max}]$ and some bad pair $(u,v)$.

Proof of Claim 8: For contradiction, we assume that $(a,b)$ is a new bad pair and $\{a,b\}\not = X_{u,v}^k$. Since $(a,b)$ is a new bad pair, $I'(a)$ is a proper subset of $I(a)$. Thus let $a\in X_{u,v}^k$ and $b\notin X_{u,v}^k$. If $a\in X_{u,v}^k$ and $|X_{u,v}^k|=2$, then $\ell (b)<\ell ({x_{u,v}^k}')$ and $r'(a)=\ell (x_{u,v}^{k-1}) < r(b)<r({x_{u,v}^k}')$, because of Claim 5(a). Thus $b\in X_{u,v}^k$, which is a contradiction. If $a\in X_{u,v}^k$ and $|X_{u,v}^k|=1$, then $\ell (b)<\ell ({x_{u,v}^k})$ and $r'(a)=\ell (x_{u,v}^{k-1}) < r(b)<r({x_{u,v}^k})$. Thus $b\in X_{u,v}^k$, which is the final contradiction.   $\Box$

In a second step, we shorten the intervals of $Y_{u,v}^{i}$ for every bad pair $(u,v)$ and $i\in [r_{u,v}^\mathrm{max}]$. Let $I'':V(G)\rightarrow \mathcal {I}^{++}$ be such that $I''(y)=[r'(y_{u,v}^{k-1}),r'(y)]$ if $y\in Y_{u,v}^k$ for some bad pair $(u,v)$ and $I''(y)=I'(y)$ else. Note that bad pairs are only referred to the interval representation $I$. Let $\ell ''(x)$ and $r''(x)$ be the left and right endpoints of the interval $I''(x)$ for $x\in V(G)$, respectively.

Claim 9

$I''$ is an interval representation of $G$.

Due to space restrictions, we omit the proof of Claim 9.

Claim 10

The change of the interval representation of $G$ from $I$ to $I''$ creates no new bad pair $(a,b)$ such that $\{a,b\}\not = X_{u,v}^k$ for some $k\in [\ell _{u,v}^\mathrm{max}]$ or $\{a,b\}\not = Y_{u,v}^i$ for some $i\in [r_{u,v}^\mathrm{max}]$ and some bad pair $(u,v)$.

Proof of Claim 10: For contradiction, we assume that $(a,b)$ is a new bad pair and $Y_{u,v}^i\not =\{a,b\}\not = X_{u,v}^k$. Thus $a\in X_{u,v}^k$ or $a\in Y_{u,v}^i$ and $b\notin X_{u,v}^k$ or $b\notin Y_{u,v}^i$, respectively. If $a\in X_{u,v}^k$ and $|X_{u,v}^k|=2$, then $\ell (b)<\ell ({x_{u,v}^k}')$ and $\ell (x_{u,v}^{k-1}) < r(b)<r({x_{u,v}^k}')$. Thus $b\in X_{u,v}^k$, which is a contradiction. If $a\in X_{u,v}^k$ and $|X_{u,v}^k|=1$, then $\ell (b)<\ell ({x_{u,v}^k})$ and $\ell (x_{u,v}^{k-1}) < r(b)<r({x_{u,v}^k})$. Thus $b\in X_{u,v}^k$, which is a contradiction. If $a\in Y_{u,v}^i$ the proof is almost exactly the same.   $\Box$

Now we are in a position to blow up some intervals to open or half-open intervals to get a mixed proper interval graph. Let $I^*: V(G)\rightarrow \mathcal {I}$ be such that

$$\begin{aligned} I^*(x)= \left\{ \begin{array}{rl} (\ell (v),r(v)), &{} \text {if } (x,v) \text { is a bad pair},\\ (\ell ''(x_{u,v}^k),r''(x_{u,v}^k)], &{} \text {if } x={x_{u,v}^k}' \text { for some bad pair } (u,v) \text { and }\\ &{}k\in [\ell _{u,v}^\mathrm{max}-1],\\ \left[ \ell ''(y_{u,v}^i),r''(y_{u,v}^i)\right) , &{} \text {if } x={y_{u,v}^i}' \text { for some bad pair } (u,v) \text { and }\\ &{} i\in [r_{u,v}^\mathrm{max}-1],\\ \left[ \ell ''(x),r''(x)\right] , &{} \text {else.} \end{array} \right. \end{aligned}$$

Note that $I^*$ is well-defined by Claims 5 and 6; that is, the four cases in the definition of $I^*$ induces a partition of the vertex set of $G$. Moreover, the interval representation $I^*$ defines a mixed proper interval graph. As a final step, we prove that $I''$ and $I^*$ define the same graph. Since we make every interval bigger, we show that for every two vertices $a,b$ such that $I''(a)\cap I''(b)=\emptyset$, we still have $I^*(a)\cap I^*(b)=\emptyset$. For contradiction, we assume the opposite. Let $a,b$ be two vertices such that $I''(a)\cap I''(b)=\emptyset$ and $I^*(a)\cap I^*(b)\not =\emptyset$. It follows by our approach and definition of our interval representation $I''$, that both $a$ and $b$ are blown up intervals.

First we suppose $a$ and $b$ are intervals that are blown up to open intervals, that is, there are distinct vertices $\tilde{a}$ and $\tilde{b}$ such that $(a,\tilde{a})$ and $(b,\tilde{b})$ are bad pairs. Furthermore, the intervals of $\tilde{a}$ and $\tilde{b}$ intersect not only in one point. By Claims 2 and 3, we assume without loss of generality, that $\ell ''(\tilde{a})<\ell ''(\tilde{b})<r''(\tilde{a})<r''(\tilde{b})$. Therefore, by the construction of $I''$, we obtain $a$ is adjacent to $\tilde{b}$ and $\tilde{a}$ is adjacent to $b$, and in addition they intersect in one point, respectively. Now, $G[\{x_{a,\tilde{a}}^1,a,\tilde{a},b,\tilde{b},y_{b,\tilde{b}}^1\}]$ is isomorphic to $T_{0,0}$, which is a contradiction.

Now we suppose $a$ is blown up to an open interval and $b$ is blown up to an open-closed interval (the case closed-open is exactly symmetric). Let $\tilde{a}$ be the vertex such that $(a,\tilde{a})$ is a bad pair. Let $\tilde{b},u,v\in V(G)$ and $k\in \mathbb {N}$ such that $\{b,\tilde{b}\}=X_{u,v}^k$. We suppose $\tilde{a}\not =\tilde{b}$. We conclude $\ell ''(\tilde{a})<\ell ''(\tilde{b})<r''(\tilde{a})<r''(\tilde{b})$. As above, we conclude $a$ is adjacent to $\tilde{b}$ and $\tilde{a}$ is adjacent to $b$, and in addition they intersect in one point, respectively. Thus $G[\{x_{a,\tilde{a}}^1,a,\tilde{a},v,u,y_{u,v}^1\}\cup \bigcup _{i=1}^k X_{u,v}^i]$ induces a $T_{k,0}$, which is a contradiction. Now we suppose $\tilde{a}=\tilde{b}$. We conclude that $G[\{x_{a,\tilde{a}}^1,a,v,u,y_{u,v}^1\}\cup \bigcup _{i=1}^{k} X_{u,v}^i]$ is isomorphic to $R_k$, which is a contradiction.

It is easy to see that $a$ and $b$ cannot be both blown up to closed-open or both open-closed intervals, because $G$ is $R_k$-free for $k\ge 0$ and the definition of $I''$.

Therefore, we consider finally the case that $a$ is blown up to a closed-open and $b$ to an open-closed interval. Let $\tilde{a},\tilde{b},u,v,w,z \in V(G)$ and $k,\tilde{k}\in \mathbb {N}$ such that $\{a,\tilde{a}\}=Y_{u,v}^k$ and $\{b,\tilde{b}\}=X_{w,z}^{\tilde{k}}$. First we suppose $\tilde{a}\not =\tilde{b}$. Again, we obtain $\ell ''(\tilde{a})<\ell ''(\tilde{b})<r''(\tilde{a})<r''(\tilde{b})$ and $a$ is adjacent to $\tilde{b}$ and $\tilde{a}$ is adjacent to $b$, and furthermore they intersect in one point, respectively. Thus $G[\{x_{u,v}^1,u,v,w,z,y_{w,z}^1\}\cup \bigcup _{i=1}^k Y_{u,v}^i\cup \bigcup _{i=1}^{\tilde{k}} X_{w,z}^i]$ is isomorphic to $T_{k,\tilde{k}}$. Next we suppose $\tilde{a}=\tilde{b}$ and hence $G[\{x_{u,v}^1,u,v,w,z,y_{w,z}^1\}\cup \bigcup _{i=1}^k Y_{u,v}^i\cup \bigcup _{i=1}^{\tilde{k}} X_{w,z}^i]$ is isomorphic to $R_{k+\tilde{k}}$. This is the final contradiction and completes the proof of Theorem 7.   $\Box$

Fig. 8.

The class $\mathcal {S}_i''$.

Fig. 9.

The graph $G_1$.

In Theorem 7 we only consider twin-free $\mathcal {U}$-graphs to reduce the number of case distinctions in the proof. In Corollary 8 we resolve this technical condition. See Figs. 8 and 9 for illustration. Let $\mathcal {S''}=\bigcup _{i=2}^{\infty }\{S_i''\}$. For the sake of space restrictions, we omit the proof.

Corollary 8

A graph $G$ is a mixed unit interval graph if and only if $G$ is a $\{G_1\}\cup \mathcal {R}\cup \mathcal {S}\cup \mathcal {S''}\cup \mathcal {T}$-free interval graph.

It is possible to extract a polynomial-time algorithm from the proof of Theorem 7. Given a graph $G$, then first start with a polynomial-time algorithm [2] which decides whether $G$ is an interval graph and if yes computes an interval representation $I$ of $G$. Second, go along the claims of Theorem 7. By suitable modifications of $I$ either $I$ becomes a mixed proper interval representation or the algorithm finds a forbidden induced subgraph. Note that by Theorem 4, the class of mixed proper interval graphs coincides with the class of mixed unit interval graphs.

Theorem 9

There is a polynomial-time algorithm which decides whether a graph has an interval representation using unit intervals only.

Remark 1: I was informed by Alan Shuchat, Randy Shull, Ann Trenk and Lee West that they independently found a proof for a characterization of mixed unit interval graphs by forbidden induced subgraphs.

Remark 2: A full version of this paper appeared in [7].