Mixed Unit Interval Bigraphs

Abstract

The class of intersection bigraphs of unit intervals of the real line whose ends may be open or closed is called mixed unit interval bigraphs. This class of bigraphs is a strict superclass of the class of unit interval bigraphs. We provide several infinite families of forbidden induced subgraphs of mixed unit interval bigraphs. We also pose a conjecture concerning characterization of mixed unit interval bigraphs and verify parts of it.

1 Introduction

Interval graphs are the intersection graphs of intervals of the real line. Unit interval graphs are interval graphs where all the intervals are of unit length. Proper interval graphs are interval graphs where no interval is properly contained in another. Interval graphs and their subclasses like unit/proper interval graphs have been extensively studied by several researchers from structural [7, 10], algorithmic [2, 3] and application [9] view point.

However, most of the researchers do not specify which type of interval is used, that is, whether the ends of the intervals are open, closed or semi-closed. This is acceptable because the class of graphs does not actually depend on this. Frankl and Meahara [8] observed that using only open intervals or only closed intervals leads to the same class of graphs. In [6] it was shown that this is even true when we allow all possible types of intervals in the intersection representation. This is no longer true for the class of unit interval graphs. Rautenbach and Szwarcfiter [15] showed that the class of intersection graphs of unit intervals of open and closed intervals is a strict superclass of the class of unit interval graphs. They also characterized this class of graphs, by a finite list of forbidden induced subgraphs. Dourado et al. [6] generalized the result of [15] to mixed unit interval graphs allowing all four distinct types of unit intervals. Felix Joos [12] gave a complete characterization of mixed unit interval graphs in terms of infinite families of forbidden induced subgraphs.

A bipartite graph (in short, bigraph) $B=(X,Y,E)$ is an interval bigraph if there exist a one-to-one correspondence between the vertex set $X\cup Y$ of B and a collection of intervals $\{I(v):v \in X \cup Y\}$ on the real line such that two vertices are adjacent if and only if their corresponding intervals intersect and they belong to different partite sets. The collection of intervals $\{I(v):v \in X \cup Y\}$ is called an interval representation of B. We simply denote the interval representation of B by I (which is a function from the vertex set $X\cup Y$ to a collection of intervals).

An interval bigraph is a unit interval bigraph if all the intervals in the interval representation are of unit length. An interval bigraph $B=(X,Y,E)$ is a proper interval bigraph if in the interval representation no interval is properly contained in another. Hell and Huang [11] proved that an interval bigraph is a unit interval bigraph if and only if it does not contain the bipartite claw $(H_1)$, the bipartite net $(H_2)$ or the bipartite tent $(H_3)$ as an induced subgraph (see Fig. 1). In [4] we observe that the bigraphs $H_1,H_2$ and $H_3$ have intersection representation with unit open and closed intervals. In the same paper we give a characterization of the class of finite intersection bigraphs of unit open and closed intervals in terms of forbidden induced bigraphs.

In the present paper we generalize the results of [4] to the mixed unit interval bigraphs where we allow all four types of unit intervals namely closed, open, left closed-right open and right closed-left open unit interval in the interval representation. Here we show that the list of forbidden induced subgraphs for mixed unit interaval bigraphs is infinite.

In Sect. 2 we introduce basic definitions, terminology, and results related to our work. In Sect. 3 we give some forbidden induced subgraphs of mixed unit interval bigraphs. In Sect. 4 we pose a conjecture concerning characterization of mixed unit interval bigraphs and verify parts of it.

2 Preliminary Results

We consider only simple, finite and connected bigraphs. For a bigraph $B=(X,Y,E)$ the neighbourhood of a vertex $u\in X\cup Y$ is denoted by $N_B(u)$. Two distinct vertices u and v of B are copies if $N_B(u)=N_B(v)$. If no two vertices of B are copies then B is copy-free. If $\mathcal {F}$ is a set of graphs and a graph G does not contain a graph in $\mathcal {F}$ as an induced subgraph then G is $\mathcal {F}$-free.

Let $\mathcal {M}$ be a family of sets. An $\mathcal {M}$-intersection representation of a bigraph is a function $f:X\cup Y \rightarrow \mathcal {M}$ such that for any two distinct vertices u and v of a bigraph B, we have $uv\in E$ if and only if $f(u)\cap f(v)\ne \emptyset$. A bigraph is an $\mathcal {M}$-bigraph if it has an $\mathcal {M}$-intersection representation.

For two real numbers a and b, we denote the open interval $\{x\in \mathbb {R}|a<x<b \}$ by (a, b), the closed interval $\{x\in \mathbb {R}|a\le x\le b \}$ by [a, b], the open-closed interval $\{x\in \mathbb {R}|a<x\le b \}$ by (a, b] and the closed-open interval $\{x\in \mathbb {R}|a\le x< b \}$ by [a, b). For an interval I, let $l(I)=\inf (I)$ and $r(I)=\sup (I)$. We suppose $\mathcal {I}^{++}$ is the set of closed intervals, $\mathcal {I}^{--}$ is the set of open intervals, $\mathcal {I}^{+-}$ is the set of closed-open intervals and $\mathcal {I}^{-+}$ is the set of open-closed intervals. Also suppose $\mathcal {U}^{++}$ is the set of unit closed intervals, $\mathcal {U}^{--}$ is the set of unit open intervals, $\mathcal {U}^{+-}$ is the set of unit closed-open intervals and $\mathcal {U}^{-+}$ is the set of unit open-closed intervals. In addition, let $\mathcal {I}^\pm =\mathcal {I}^{++}\cup \mathcal {I}^{--}$, $\mathcal {U}^\pm =\mathcal {U}^{++}\cup \mathcal {U}^{--}$, $\mathcal {I}=\mathcal {I}^{++}\cup \mathcal {I}^{--} \cup \mathcal {I}^{+-} \cup \mathcal {I}^{-+}$, and $\mathcal {U}=\mathcal {U}^{++}\cup \mathcal {U}^{--}\cup \mathcal {U}^{+-}\cup \mathcal {U}^{-+}$.

Our first result shows that as in the case of interval graphs, the class of interval bigraphs does not depend on the type interval used in the intersection representation.

Proposition 1

The classes of $\mathcal {I}^{++}$-bigraphs, $\mathcal {I}^{--}$-bigraphs, $\mathcal {I}^{\pm }$-bigraphs,

$\mathcal {I}^{+-}$-bigraphs, $\mathcal {I}^{-+}$-bigraphs and $\mathcal {I}$-bigraphs are the same.

The following proposition extends the result of Proposition 2 of [6] which showed that a bigraph is a $\mathcal {U}^{++}$-bigraph if and only if it is a $\mathcal {U}^{--}$-bigraph.

Proposition 2

The classes of $\mathcal {U}^{++}$-bigraphs, $\mathcal {U}^{--}$-bigraphs, $\mathcal {U}^{+-}$-bigraphs,

$\mathcal {U}^{-+}$-bigraphs and $\mathcal {U}^{+-}\cup \mathcal {U}^{-+}$-bigraphs are the same.

The proofs of the above propositions are similar to the proof of Dourado et al. [6] and so omitted.

Fig. 1.

The bipartite claw $(H_1)$, net $(H_2)$ and tent $(H_3)$

Interval bigraphs coincide with $\mathcal {I}^{++}$-bigraphs and unit interval bigraphs coincide with $\mathcal {U}^{++}$-bigraphs. Following theorem relates the class of interval bigraphs, unit interval bigraphs and proper interval bigraphs.

Theorem 3

([11, 13, 16]). An interval bigraph is a unit interval bigraph if and only if it is a proper interval bigraph if and only if it does not contain $H_1$, $H_2$ or $H_3$ as an induced subgraph.

As mentioned in the introduction, the bigraphs $H_1$, $H_2$ and $H_3$ have $\mathcal {U}$-intersection representation; see Figs. 2, 3 and 4.

Fig. 2.

The bipartite claw $H_1$ and its $\mathcal {U}$-intersection representation.

Fig. 3.

The bipartite Net $H_2$ and its two $\mathcal {U}$-intersection representation.

Fig. 4.

The bipartite tent $H_3$ and its two $\mathcal {U}$-intersection representation.

As observed in [4] each intersection representation of $H_1$, $H_2$ and $H_3$ is unique upto trivial modifications (these trivial modifications include suitable interval shifts that preserve intersections and relative positions between intervals, changes in the types (open, closed or half closed) of some intervals, reflection of the entire model about a point on the real line, translation of the entire model, and relabeling of some intervals).

Therefore the class of $\mathcal {U}^{\pm }$-bigraphs is a strict superclass of the class of unit interval bigraphs. We have characterized these class of bigraphs in [4] (Fig. 5).

For an $\mathcal {I}^{++}$-bigraph if two vertices u and v are copies then they belong to the same partite set. And in the $\mathcal {I}^{++}$-interval representation we can take same interval for these two vertices. Thus we consider that our bigraphs are copy free.

Fig. 5.

Forbidden induced subgraphs of $\mathcal {U}^\pm$-bigraphs.

Fig. 6.

The bigraph $F_3$ and its $\mathcal {U}$-intersection representation.

Theorem 4

([4]). For a copy-free bipartite graph B, the following statements are equivalent.

• (i) B is a $\{F_1,F_2,F_3,F_4,F_5,F_6,F_7,F_8,F_9,F_{10},F_{11},F_{12}\}$-free interval bigraph.

• (ii) B is an almost proper interval bigraph.

• (iii) B is a $\mathcal {U}^{++}\cup \mathcal {U}^{--}$-bigraph.

3 Forbidden Induced Subgraphs of Mixed Unit Interval Bigraphs

It can be observed that the bigraphs $F_2$, $F_4$, $F_5$, $F_8$, $F_9$, $F_{10}$, $F_{11}$ and $F_{12}$ have no $\mathcal {U}$-intersection representation. In this section we shall give some other forbidden induced subgraphs of mixed unit interval bigraphs (Figs. 7, 8, 9, 10, 11 and 12).

Fig. 7.

The class $\mathcal {L}$

Fig. 8.

The class $\mathcal {M}$.

Fig. 9.

The class $\mathcal {N}$.

Fig. 10.

The class $\mathcal {H'}$.

Fig. 11.

The bigraph $B_1$

Fig. 12.

The bigraph $B_2$

Lemma 5

The bigraph $F_1$ has unique $\mathcal {U}$-intersection upto trivial modifications.

Fig. 13.

The graph $F_1$ and its $\mathcal {U}$-representation.

Proof

The proof follows from the Proposition 5 of [4]. The bigraph $F_1-y_3$ is the bipartite claw $(H_1)$. Thus from that Proposition, $H_1$ has a unique $\mathcal {U}$-intersection as shown in Fig. 2. Since the vertex $y_3$ is adjacent to $x_1$ only, so we can take $I(y_3)$ as in Fig. 13 to get the $\mathcal {U}$-intersection representation of $F_1$. Again $I(y_3)$ can be taken as closed-open copy of $I(y_2)$ and make some trivial modifications to get the same representation of $F_1$ as earlier. This completes the proof.   $\square$

From the above Lemma we have the following corollary.

Corollary

The bigraph $B_1$ is the minimal forbidden induced subgraph of the class of $\mathcal {U}$-intersection bigraphs (Fig. 14).

Fig. 14.

The class $\mathcal {F'}$ of bigraphs

In the bigraph $F_{i,j}$, if i is even then $u\in X$ and $v',v''\in Y$; and if i is odd then $u\in Y$ and $v',v''\in X$. Similarly if j is even then $w\in X$ and if j is odd then $w\in Y$ and w, z are vertices of different partite sets. The two vertices $v'$ and $v''$ are the special vertices of $F_{i,j}$. In the next lemma, we show that the bigraph $F_{i,j}$ has a unique $\mathcal {U}$-intersection representation upto trivial modifications.

Lemma 6

Let $i,j\in \mathbb {N}$

• (a) A $\mathcal {U}$-intersection representation $I:V(F_{i,j})\rightarrow \mathcal {U}$ of $F_{i,j}$, where $I(V(F_{i,j}))$ consists of the following intervals

  • $I(x)=I(y_0)=[0,1]$, $I(x_0)=(0,1)$, $I(y)=(-1,0]$

  • $I(y_k)=[2(k-1)+1,2(k-1)+2]$, $I(x_k)=[2(k-1)+2,2(k-1)+3]$, $(k\ge 1)$

  • $I(x_k')=(2(k-1)+1,2(k-1)+2)$, $I(y_k')=(2(k-1)+2,2(k-1)+3)$, $(k\ge 1)$

  • $I(y_k'')=[-2(k-1)-1,-2(k-1)]$, $I(x_k'')=[-2(k-1)-2,-2(k-1)-1]$, $(k\ge 1)$

  • $I(x_k''')=(-2(k-1)-2,-2(k-1)-1]$, $I(y_k''')=(-2k-1,-2k]$, $(k\ge 1)$

  • $I(w)=[j,j+1],\ I(z'')=I(w'')=(j,j+1),\ I(z')=[j+1,j+2],\ I(w')=[j+2,j+3]\ \mathrm {or}\ [j+2,j+3)$ and

  • $I(u)=[-i,-i+1],\ I(v')=I(v'')=[-i-1,-i]\ \mathrm {or}\ (-i-1,-i]$

  is unique upto trivial modifications.

• (b) $L_{i,j}$ is a minimal forbidden induced subgraph for the class of $\mathcal {U}$-bigraphs.

Proof

(a) It can be easily observed that every $F_{i,j}$ contains $F_1$ as an induced subgraph. Consider $F_{1,1}$, it contains $F_1$ as an induced subgraph, where $V(F_1) = \{x_0,y_0,x,y,y_1,y_1'',x_0',x'\}$. Without loss of generality we consider the $\mathcal {U}$-inter-section of $F_1$ for the vertices $x_0,y_0,x,y,y_1, y_1'',x_0',x'$ as follows: $I(x)=I(y_0)=[0,1]$, $I(x_0)=(0,1)$, $I(y_1)=[1,2]$, $I(x')=[2,3]$, $I(y'')=[-1,0]$, $I(y)=(-1,0]$, $I(x_0')=[-2,-1] \text { or } (-2,-1]$. Next we take $I(x'')=I(y'')=(1,2)$, $I(y')=[3,4] \text{ or } [3,4)$ and $I(x_0'')=I(x_0')$. Now consider $F_{i,j}$ and let $j=2n$. Then $w=x_n$, and the path $y_1,x_1,y_2,x_2,\ldots ,y_k,x_k,\ldots ,y_n,x_n$ has the representation $I(y_1)=[1,2]$, $I(x_1)=[2,3]$, $I(y_2)=[3,4]$, $I(x_2)=[4,5]$, and by induction $I(y_k)=[2(k-1)+1,2(k-1)+2]$ and $I(x_k)=[2(k-1)+2,2(k-1)+3]$. Then we have $I(x_n)=[2(n-1)+2,2(n-1)+3]=[2n,2n+1]$. In the other case, if $j=2n+1$, then $w=y_{n+1}$ and we have $I(y_{n+1})=[2(n+1-1)+1,2n+2]=[2n+1,2n+2]$. Thus $I(w)=[j,j+1],\ I(z')=[j+1,j+2],\ I(w')=[j+2,j+3]$ or $[j+2,j+3)$. As $z''$ is adjacent to w only in this path and $w''$ is adjacent to $z''$ so we take $I(z'')=I(w'')=(j,j+1)$. As the vertices $x_0,y_0,x,y$ belong to $F_{i,j}$, we take the interval representation of these vertices as before (i.e. as in the case of $F_{1,1}$).

Next $x_k'$ is adjacent to $y_k$ and $y_k'$ is adjacent to $x_k$ only so we take $I(x_k')$ as the open copy of $I(y_k)$ and $I(y_k')$ as the open copy of $I(x_k)$. Again consider the path $x,y_1'',x_1'',\ldots ,y_k'',x_k'',\ldots ,u$. As $I(x)=[0,1]$ we take the interval representation of $I(y_1'')=[-1,0],\ I(x_1'')=[-2,-1]$, $I(y_2'')=[-3,-2],\ I(x_2'')=[-4,-3]$, and by induction $I(y_k'')=[-2(k-1)-1,-2(k-1)]$ and $I(x_k'')=[-2(k-1)-2,-2(k-1)-1]$. If $i=2m$, then $u=x_m$; so $I(u)=I(x_m)=[-2(m-1)-2,-2(m-1)-1]=[-2m,-2m+1]$. And if $i=2m+1$, then $u=y_{m+1}$, so $I(u)=[-2(m+1-1)-1,-2(m+1-1)]=[-2m-1,-2m]$. Thus $I(u)=[-i,-i+1]$ and $I(v_0')$ and $I(v_0'')=[-i-1,-i]$ or $(-i-1,-i]$. Finally, $x_k'''$ is adjacent to $y_k''$ only and $y_k'''$ is adjacent to $x_k''$ only. So we take $I(x_k''')$ as the open-closed copy of $I(x_k'')$ and $I(y_k''')$ as the open-closed copy of $I(y_{k+1}'')$. Which completes the proof of (a).

(b) $L_{i,j}$ is obtained from $F_{i,j}$ by adjoining two distinct vertices $u'$ and $u''$ with $v'$ and $v''$, where $u'$ is adjacent to $v'$ and $u''$ is adjacent to $v''$. Thus from $\mathcal {U}$-intersection representation of $F_{i,j}$, it follows that $L_{i,j}$ is the minimal forbidden induced subgraph of $\mathcal {U}$-bigraphs.   $\square$

As before the two vertices $v'$ and $v''$ are the special vertices of $M_i'$. In the following lemma we show that the bigraph $M_i'$ has a unique $\mathcal {U}$-intersection representation upto trivial modifications.

Lemma 7

Let $i\in \mathbb {N}$

• (a) A $\mathcal {U}$-intersection representation $I:V(M_i')\rightarrow \mathcal {U}$ of $M_i'$, where $I(V(M_i'))$ consists of the following intervals

  • $I(x_2'')=I(y_4'')=[0,1],\ I(x_3'')=I(y_1)=[1,2],\ I(y_2'')=[-1,0]$ or $(-1,0],\ I(y_3'')=(1,2)$

  • $I(x_k)=[2k,2k+1],\ I(x_k')=[2k,2k+1),\ (k\ge 1)$

  • $I(y_k)=[2k-1,2k],\ I(y_{k-1}')=[2k-1,2k),\ (k\ge 2)$ and

  • $I(u)=[i+1,i+2],\ I(v')=I(v'')=[i+2,i+3]$ or $[i+2,i+3)$

  is unique upto trivial modifications.

• (b) $M_i$ is a minimal forbidden induced subgraph for the class of $\mathcal {U}$-bigraphs (Fig. 15).

Fig. 15.

The class $\mathcal {M'}$ of bigraphs.

Proof

(a) It can be easily observed that the bigraph $M_i'$ contains $H_2$ as an induced subgraph, where $V(H_2)=\{x_1,y_1,x_2'',y_2'',x_3'',y_3'',y_4''\}$. From Proposition 6 of [4] we take the intervals corresponding to these vertices as $I(x_2'')=I(y_4'')=[0,1],\ I(y_2'')=[-1,0]$ or $(-1,0],\ I(x_3'')=I(y_1)=[1,2],\ I(y_3')=(1,2),\ I(x_1)=[2,3]$. As $x_1'$ is adjacent to $y_1$ only we must take $I(x_1')=[2,3)$. In $M_i'$ consider the path $P:y_1,x_1,y_2,x_2,\ldots ,y_k,x_k,\dots ,u$. If $i=2n$, then $u=y_{n+1}$ and if $i=2n+1$, then $u=x_{n+1}$. Now intervals corresponding to the vertices $y_2,x_2,y_3,x_3$ are $I(y_2)=[3,4],\ I(x_2)=[4,5],\ I(y_3)=[5,6],\ I(x_3)=[6,7]$. Thus by induction, $I(y_k)=[2k-1,2k]$ and $I(x_k)=[2k,2k+1]$. Hence $I(y_{n+1})=[2n+1,2n+2]$ and $I(x_{n+1})=[2n+2,2n+3]$.

Thus $I(u)=[i+1,i+2]$ and I(v) and $I(v'')=[i+2,i+3]$ or $[i+2,i+3)$. Now $x_k'$ is adjacent to $y_k$ only so we take $I(x_k')$ as the closed-open copy of $I(x_k)$. Again $y_{k-1}'$ is adjacent to $x_{k-1}$ only, and as $y_k$ is adjacent to $x_{k-1}$ in P. So we take $I(y_{k-1}')$ as the closed-open copy of $I(y_k),\ (k\ge 2)$. This completes the proof of (a).

(b) From the above representation of $M_i'$ it follows that $M_i$ has no $\mathcal {U}$-intersection representation and hence $M_i$ is a minimal forbidden induced subgraph for the class of $\mathcal {U}$-bigraphs.   $\square$

The vertices $v'$ and $v''$ are the special vertices of $N_i'$. In the next lemma we show that the bigraph $N_i'$ has a unique $\mathcal {U}$-intersection representation upto trivial modifications.

Lemma 8

Let $i\in \mathbb {N}$.

• (a) A $\mathcal {U}$-intersection representation $I:V(N_i')\rightarrow \mathcal {U}$ of $N_i'$, where $I(V(N_i'))$ consists of the following intervals

  • $I(x_2'')=I(y_2'')=[-2,-1],\ I(x_4'')=I(y_1'')=[-1,0],\ I(x_1'')=(-1,0)$

  • $I(x_3'')=[0,1],\ I(y_3'')=[0,1)$

  • $I(y_4'')=[-3,-2]$ or $(-3,2]$

  • $I(y_k)=[2k-2,2k-1],\ I(x_k)=[2k-1,2k],\ (k\ge 1)$

  • $I(x_k')=[2k-1,2k),\ (k\ge 1)$ and $I(y_k')=[2k-2,2k-1),\ (k\ge 2)$ and

  • $I(u)=[i-1,i],\ I(v')$ and $I(v'')=[i,i+1]$ or $[i,i+1)$

  is unique upto trivial modifications.

• (b) $N_i$ is a minimal forbidden induced subgraph for the class of $\mathcal {U}$-bigraphs (Fig. 16).

Fig. 16.

The class $\mathcal {N'}$ of bigraphs.

Proof

(a) It is easy to obeserve that each of the bigraph $N_i'$ contains the graph $H_3+y_4''$ as an induced subgraph, where $V(H_3+y_4'')=\{x_1'',y_1'',x_2'',y_2'',x_3'',y_3'',x_4'', y_4''\}$. Without loss of generality we take the following representation of $H_3+y_4''$. Where $I(y_2'')=I(x_2'')=[-2,-1],\ I(x_4'')=I(y_1'')=[-1,0],\ I(x_1'')=(-1,0),\ I(x_3'')=[0,1]$ and $I(y_3'')=[0,1)$. As $y_1$ is adjacent to $x_3''$ and $x_4''$ and $x_1$ is adjacent to $y_1$ so we take $I(y_1)=[0,1]$ and $I(x_1)=[1,2]$. Again as $y_2$ is adjacent to $x_1$, $x_2$ is adjacent to $y_2$ and so on; we can take the interval representation of the path $y_1,x_1,y_2,x_2,\ldots ,y_k,x_k,\ldots ,u$ where $I(y_1)=[0,1],\ I(x_1)=[1,2],\ I(y_2)=[2,3],\ I(x_2)=[3,4]$. And by induction, we have $I(y_k)=[2k-2,2k-1]$ and $I(x_k)=[2k-1,2k]$. Now if $i=2m$, then $u=x_m$. Then $I(x_m)=[2m-1,2m]=[i-1,i]$. In the other case, if $i=2m-1$, then $u=y_m$. And $I(y_m)=[2m-2,2m-1]=[i-1,i]$. As v and $v'$ are adjacent to u, we take $I(v)=I(v')=[i,i+1]$ or $[i,i+1)$. Again as $x_k'$ is adjacent to $y_k$ only also $y_k$ is adjacent to $x_k$ we take $I(x_k')=[2k-1,2k),\ (k\ge 1)$. As $y_k'$ is adjacent to only $x_{k-1}$ also $x_{k-1}$ is adjacent to $y_k$, we take $I(y_k')=[2k-2,2k-1),\ (k\ge 2)$. This completes the proof of (a).

(b) From the representation of $N_i'$ it follows that $N_i$ is the minimal forbidden induced subgraphs for $\mathcal {U}$-bigraphs.   $\square$

The two vertices $v'$ and $v''$ are the special vertices of $H_i''$. In the next lemma we show that the bigraph $H_i''$ has a unique $\mathcal {U}$-intersection representation upto trivial modifications.

Lemma 9

Let $i\in \mathbb {N}$.

• (a) A $\mathcal {U}$-intersection representation $I:V(H_i'')\rightarrow \mathcal {U}$ of $H_i''$, where $I(V(H_i''))$ consists of the following intervals

  • $I(x_2'')=[-1,0]$ or $(-1,0]$, $I(y_2'')=[-1,0]$ or $(-1,0]$

  • $I(x_4'')=I(y_1'')=[0,1],\ I(y_3'')=(0,1),\ I(x_3'')=[\frac{1}{2},\frac{3}{2}]$

  • $I(x_1)=[1,2],\ I(x_1'')=[1,2)$

  • $I(x_k)=[2k-1,2k],\ I(y_k)=[2k,2k+1],\ (k\ge 1)$

  • $I(y_k')=[2k,2k+1),\ I(x_k')=[2k+1,2k+2),\ (k\ge 1)$

  • $I(u)=[i,i+1],\ I(v')$ and $I(v'')=[i+1,i+2]$ or $[i+1,i+2)$

  is unique upto trivial modifications.

• (b) $H_i'$ is a minimal forbidden induced subgraph for $\mathcal {U}$-bigraph (Fig. 17).

Fig. 17.

The class $\mathcal {H''}$ of bigraphs.

Proof

(a) Every $H_i''$ contains $H_3$ as an induced subgraph, where $V(H_3)$ is $\{x_2'',y_2'',x_3'',y_3'',x_4'',y_1'',x_1\}$. Consider the following representation of $H_3$, where $I(x_2'')=I(y_2'')=[-1,0] \text{ or } (-1,0]$, $I(x_4'')=I(y_1'')=[0,1]$, $I(y_3'')=(0,1)$, $I(x_3'')=[\frac{1}{2},\frac{3}{2}]$, $I(x_1)=[1,2]$. Next, consider the interval representation of the path $y_1'',x_1,y_1,x_2,y_2,\ldots , x_k,y_k,\ldots ,u$, where $I(x_1)=[1,2]$, $I(y_1)=[2,3]$, $I(x_2)=[3,4]$, $I(y_2)=[4,5]$. And by induction $I(x_k)=[2k-1,2k],\ I(y_k)=[2k,2k+1],\ (k\ge 1)$. For the ith vertex u, if $i=2m$ then $u\in Y$ and $u=y_m$, and $I(u)=[2m,2m+1]=[i,i+1]$. Again if $i=2m+1$, $u\in X$ and $u=x_{m+1}$, then $I(u)=[2(m+1)-1,2(m+1)]=[2m+1,2m+1+1]=[i,i+1]$. Consequently $I(v')$ and $I(v'')$ are $[i+1,i+2]$ or $[i+1,I+2)$. Again $x_1''$ is adjacent to $y_1''$ only so $I(x_1'')=[1,2)$. Similarly $y_k'$ is adjacent to $x_k$ only so $I(y_k')=[2k,2k+1)$ as $y_k$ is also adjacent to $x_k$. Next $x_k'$ is adjacent to $y_k$ and $x_{k+1}$ is also adjacent to $y_k$, so $I(x_k')=[2k+1,2k+2),\ (k\ge 1)$, this completes the proof of (a).

(b) From the $\mathcal {U}$-representation of $H_i''$ it follows that $H_i'$ is minimal induced forbidden subgraph for $\mathcal {U}$-bigraphs.   $\square$

Lemma 10

The bigraph $B_2$ is minimal forbidden induced subgraph for $\mathcal {U}$- bigra-phs.

Proof

$B_2$ contains $H_1$ as an induced subgraph, where $V(H_1)=\{y,x,y_1,x_2,y_2,x_2',y_2'\}$. As $H_1$ has a unique $\mathcal {U}^\pm$-representation upto trivial modifications, we take the following representation of it, $I(x)=I(y_1)=[1,2],\ I(y)=(1,2),\ I(x_2)=[0,1],\ I(x_2')=[2,3]$ and $I(y_2)=[-1,0]$ or $(-1,0],\ I(y_2')=[3,4]$ or [3, 4). As $x_3$ is adjacent to $y_1$ but not to $y_2$ we take $I(x_3)=(0,1]$. Similarly $I(x_3')=[2,3)$. Again as $y_4$ is adjacent to $x_2$ and $x_3$ only so we may take $I(y_4)=(0,1)$. Similarly $I(y_4')=(2,3)$. Now it is not possible to give an interval representation for the vertex $x_1$.

Also it may be noted that $B_2$ contains $H_2-y_3$ as an induced subgraph, where $V(H_2-y_3)=\{x_1,y_1,x_2,y_2,x_3,y_4\}$. Consider the representation of $H_2-y_3$, where $I(x_3)=[1,2],\ I(x_1)=(1,2)$ or $(1,2],\ I(y_1)=[1,2],\ I(x_2)=[0,1],\ I(y_4)=[0,1],\ I(y_2)=[-1,0]$ or $(-1,0]$. Now $x_2'$ and $x_3'$ are adjacent to $y_1$ and $y_2'$ is adjacent to $x_2'$. So we take $I(x_2')=[2,3],\ I(x_3')=[2,3),\ I(y_2')=[3,4]$ or [3, 4). Again $y_4'$ is adjacent to $x_2'$ and $x_3'$ only so $I(y_4')=(2,3)$. As x is adjacent to $y_1$ only so we take $I(x)=(1,2)$. But now, it is not possible to give an interval representation for the vertex y. Also it can be verified that for other representation of $H_2-y_3$, it is not possible to give an interval representation of $B_2$. This completes the proof of the lemma.   $\square$

Fig. 18.

The bigraph $B_0$

Lemma 11

In the bigraphs $F_{i,j},\ M_i',\ N_i',\ H_i''$ if we have the bigraph $B_0$ containing u as an induced subgraph (the vertices $v'$ and $v''$ are absent) then the resulting bigraphs are still minimal forbidden induced subgraphs for $\mathcal {U}$-bigraphs (u and v are vertices of different partite sets) (Fig. 18).

Proof

In the $\mathcal {U}$-intersection representation of any of the bigraphs $F_{i,j},\ M_i',\ N_i'$ or $H_i''$, let the interval corresponding to u is $I(u)=[a,a+1]$. As $v_0'$ and $v_0''$ are adjacent to u, $u_0$ is adjacent to $v_0'$, $v_0''$ and $u_0'$ is adjacent to $v_0''$ only, we take intervals corresponding to these vertices as follows: $I(v_0'')=[a+1,a+2],\ I(v_0')=[a+1,a+2),\ I(u_0)=(a+1,a+2)$ and $I(u_0')=[a+2,a+3]$ or $[a+2,a+3)$. Now the interval representation of $v_0$ is not possible as there exists an interval $I(u')=[a,a+1)$ in the interval representation of each of the bigraphs $F_{i,j},\ M_i',\ N_i',\ H_i''$. This completes the proof of the lemma.   $\square$

4 A Conjecture for Mixed Unit Interval Bigraphs

In the previous Section we have seen that the bigraphs $F_2,F_4,F_5,F_8,F_9,F_{10},F_{11}$, $F_{12},B_1$ and $B_2$ are minimal forbidden induced subgraphs for $\mathcal {U}$-bigraphs. Also several infinite families of bigraphs, namely, $\mathcal {L},\mathcal {M},\mathcal {N},\mathcal {H}'$ that are the forbidden families of $\mathcal {U}$-bigraphs. Next, we observe that in the bigraph $F_{i,j}$, the vertex u is adjacent to two special vertices $v'$ and $v''$. Now if there exist two distinct vertices $u'$ and $u''$ such that $u'$ is adjacent to $v'$ and $u''$ is adjacent to $v''$ we have the bigraph $L_{i,j}$. Similar observation can be made for the bigraphs $M_i,N_i$ and $H_i''$. Also in the Lemma 11, we proved that for the bigraphs $F_{i,j},M_i',N_i',H_i''$ where vertices $v'$ and $v''$ are deleted, if we have the bigraph $B_0$ as an induced subgraph containing the vertex u, then the resulting graph is also a forbidden induced subgraph for $\mathcal {U}$-bigraphs. These results inspire us to pose a conjecture. But before that we introduce a new definition. For notational convenience we write $l(I(v))=l(v)$ and $r(I(v))=r(v)$

A bigraph $B=(X,Y,E)$ is a mixed proper interval bigraph if it has an $\mathcal {I}$-intersection representation $I:V(B)\rightarrow \mathcal {I}$ such that

• (i) for two distinct vertices u and v of B with $I(u),I(v)\in \mathcal {I}^{++},\ I(u)\not \subset I(v)$ and $I(v)\not \subset I(u)$, and

• (ii) for every vertex u of B with $I(u)\not \in \mathcal {I}^{++}$, there is a vertex v of B with $I(v)\in \mathcal {I}^{++},\ l(u)=l(v)$ and $r(u)=r(v)$, that is no closed interval is properly contained in another closed interval and for any non closed interval, there is a closed interval with same end point.

Let $\mathcal {B'}$ be the class of bigraphs, where $\mathcal {B'}=\mathcal {F'}\cup \mathcal {M'}\cup \mathcal {N'}\cup \mathcal {H''}$. We are now in a position to phrase our conjecture.

Conjecture 12

For a bigraph B, the following statements are equivalent.

• (a)

  • B is $\{B_1,B_2,F_2,F_4,F_5,F_8,F_9,F_{10},F_{11},F_{12}\}\cup \mathcal {L}\cup \mathcal {M}\cup \mathcal {N}\cup \mathcal {H'}$-free interval bigraph and

  • for every induced subgraph H of B that is isomorphic to one of the bigraphs of the class $\mathcal {B'}$ and any vertex $u^*\in V(B)\setminus V(H)$ is such that $u^*$ is adjacent to exactly one of the special vertices of H,

  • if $H'=H\setminus \{v',v''\}$ then $H'\cup B_0$ is not an induced subgraph of B.

• (b) B is a mixed proper interval bigraph.

• (c) B is a mixed unit interval bigraph.

In the last two results we verify the conjecture partly and we leave open the problem of finding the complete list of forbidden bigraphs of mixed unit interval bigraphs.

Proposition 13

The implication $(c)\Rightarrow (a)$ of Conjecture 12 is true.

Proof

Let B be a $\mathcal {U}$-bigraph, and let I be a $\mathcal {U}$-intersection representation of B. Then obviously B is $F_2, F_4$, $F_5,F_8,F_9,F_{10},F_{11},F_{12}$-free interval bigraphs. Also corollary of Lemmas 5 and 10 imply that B is $B_1$ and $B_2$-free. And from Lemmata 6, 7, 8 and 9, B is $\mathcal {L}\cup \mathcal {M}\cup \mathcal {N}\cup \mathcal {H'}$-free interval bigraph

Now the H be an induced subgraph of B that is isomorphic to any bigraph of the class $\mathcal {B'}$. Let the vertices in H be denoted as in the definition of the bigraphs in the class $\mathcal {B'}$. Then the two pendant vertices $v'$ and $v''$ are special vertices which are adjacent to u. And $v',v'',u\in V(H)$. Let $u^*\in V(B)\setminus V(H)$ be such that $u^*$ is adjacent to $v'$ but not to $v''$. By Lemmata 6, 7, 8 and 9 we may assume that $I(v')=[a,a+1]$ and $I(v'')=[a,a+1)$, where $a\in \mathbb {R}$. $r(I(v))\le a$ for any $v\in V(H)\setminus \{v',v''\}$. Thus $I(u^*)$ can be taken as any of intervals $[a+1,a+2]$ or $[a+1,a+2)$ and this implies that $u^*$ is adjacent to $v'$ only. From Lemma 11, it follows that $H'\cup B_0$ is forbidden induced subgraph of B. This completes the proof.   $\square$

Theorem 14

A bigraph is a mixed proper interval bigraph if and only if it is a $\mathcal {U}$-bigraph; that is; statements (b) and (c) of Conjecture 12 are equivalent.

Proof

The ‘only if’ part of the proof is similar to the proof of Theorem 8 in [6]. For the sake of completeness, we give here details.

Let B be a mixed proper interval bigraph and I be a mixed proper interval representation of B. Let $V_1$ denote the set of vertices u of B such that $I(u)\in \mathcal {U}^{++}$. By the definition of mixed proper interval bigraphs, the subgraph $B[V_1]$ induced by the vertex set $V_1$ is a proper interval bigraph. And the interval representation of $B[V_1]$ is given by the corresponding intervals of I. Bogart and West [1], gave a constructive method how a proper interval representation $I_1$ produces to a unit interval representation $I_2$ gradually converting the intervals into unit intervals by means of successive contraction, dilations and translation. In this procedure it may be noted that two intervals intersect at a single point in $I_1$ if and only if the corresponding intervals intersect at a single point in $I_2$. And two intervals intersect more than one point in $I_1$ if and only if corresponding intervals intersects more than one point in $I_2$. Also two intervals do not intersect in $I_1$ if and only if they do not intersect in $I_2$. This implies that reinserting the mixed intervals corresponding to the vertices in $V(B)\setminus V_1$ as mixed copies of the corresponding closed intervals results in a $\mathcal {U}$-intersection representation of B, and this completes the ‘only if’ part.

For the ‘if’ part let B be a $\mathcal {U}$-bigraph and $I:V(B)\rightarrow \mathcal {U}$-intersection representation of B. Let I(u) be an open interval of I. As I(u) is forced to be open there must exist $v_1$ and $v_2$, such that $I(v_1)$ and $I(v_2)$ are closed and $r(v_1)=l(u)$, $l(v_2)=r(u)$. Now $I(v_1)$ and $I(v_2)$ must not be moved to the left and the right respectively as then I(u) can be made to a closed interval, so there exist $u'$ such that $I(u')$ is closed and $l(u)=l(u')$, $r(u)=r(u')$, u and v vertices of different partite sets.

Next, let I(u) be an open-closed interval (i.e. l(u) is open and r(u) is closed). By the similar reason there exists a closed interval I(v) such that $l(u)=r(v)$. Since B is connected we have $I(u')$ intersecting I(v). Now $I(u')\in \mathcal {U}^{++}$ and $l(u')=l(u)$ and $r(u')=r(u)$, otherwise I(v) can be moved to the left and may makes l(u) closed. Thus for every $I(z)\not \in \mathcal {U}^{++}$, $z\in V(B)$, we have closed interval with the same end points as of I(z). This completes the proof.   $\square$

5 Conclusion

In this paper we provide some forbidden subgraphs and four infinite families of forbidden subgraphs of mixed unit interval bigraphs. We also put forward a conjecture and hope that this will motivate to give a complete characterization of the class of mixed unit interval bigraphs in terms of forbidden induced subgraphs. In an earlier paper [4] we give the forbidden subgraph characterization of unit interval bigraphs of open and closed intervals, but the forbidden subgraph characterization of interval bigraphs is an interesting open problem. In [5] Das et al. have made considerable progress to solve it. The complexity of the only known recognition of interval bigraphs given by Müller [14] is very high. The problem of finding a recognition algorithm for interval graphs (or bigraphs) of open and closed intervals is still open. However, in a very recent paper [17] Talon and Kratochvíl have given a quadratic-time algorithm to recognize the class of mixed unit interval graphs.