#  $2$-nested matrices: towards understanding the structure of circle graphs

Guillermo Durán1,2,3 and Nina Pardal1,4 and Martín D. Safe5,6 1 CONICET-
Universidad de Buenos Aires, Instituto de Cálculo (IC), Buenos Aires,
Argentina
2 Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales,
Departamento de Matemática, Buenos Aires, Argentina
3 Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y
Matemáticas, Universidad de Chile, Santiago, Chile
4 CONICET-Universidad de Buenos Aires, Instituto de Investigación en Ciencias
de la Computación (ICC), Buenos Aires, Argentina
5 Departamento de Matemática, Universidad Nacional del Sur (UNS), Bahía
Blanca, Argentina
6 INMABB, Universidad Nacional del Sur (UNS)-CONICET, Bahía Blanca, Argentina

###### Abstract

A $(0,1)$-matrix has the _consecutive-ones property_ (C$1$P) if its columns
can be permuted to make the $1$’s in each row appear consecutively. This
property was characterised in terms of forbidden submatrices by Tucker in
1972. Several graph classes were characterised by means of this property,
including interval graphs and strongly chordal digraphs.

In this work, we define and characterise $2$-nested matrices, which are
$(0,1)$-matrices with a variant of the C$1$P and for which there is also
certain assignment of one of two colors to each block of consecutive $1$’s in
each row. The characterization of $2$-nested matrices in the present work is
of key importance to characterise split graphs that are also circle by minimal
forbidden induced subgraphs.

###### keywords:

consecutive-ones property, circle graphs, split graphs, $2$-nested matrices

##  1 Introduction

A $(0,1)$-matrix has the _consecutive-ones property_ (C$1$P) if there is a
permutation of its columns such that the $1$’s in each row appear
consecutively. It appears naturally in a wide range of applications, and more
precisely, in any problem in which we are required to linearly arrange a set
of objects with the restriction that some sets of objects must appear
consecutively [1, 13, 11].

The C$1$P has been widely studied. The matrices with this property were
studied by Fulkerson and Gross in [8], where a characterization of interval
graphs in terms of the C$1$P of their clique-matrices was given. The C$1$P,
along with some variants of it, has been widely used to study structural
properties of several other graph classes, such as proper interval graphs
[16], proper interval bigraphs [17], strongly chordal digraphs [12], and
adjusted interval digraphs [6]. In 1972, Tucker [18] presented a
characterization of the C$1$P in terms of forbidden submatrices. The
corresponding forbidden matrices were later called _Tucker matrices_.

In this work, we define and characterise $2$-nested matrices, which are
$(0,1)$-matrices with a variant of the C$1$P and for which there is also a
particular assignment of one of two colors to each block of consecutive $1$’s
in each row. This characterization is a continuation of the work in [15]. A
graph is _circle_ [4] if it is the intersection graph of a set of chords on a
circle; if so, the set of chords is called a _circle model_ of the graph. A
_split graph_ [7] is any graph $G$ admitting a _split partition_ $(K,S)$, i.e.
a partition of its vertex set into a clique $K$ and a stable set $S$; we
denote it by $G=(K,S)$. In [2, 14], we addressed the problem of characterizing
those split graphs that are also circle by strongly relying on the
characterization of $2$-nested graphs proved in the current paper. We now
briefly introduce the connection between split graphs that are circle graphs
and $2$-nested matrices.

Let us first consider a split graph $G$ that is _minimally non-circle_ , i.e.
$G$ is non-circle but any proper induced subgraph of $G$ is circle.
_Permutation graphs_ are exactly those comparability graphs whose complement
is also a comparability graph [5]. Since permutation graphs are circle (see
e.g. [10, p. 252]) and $G$ is non-circle, $G$ is not a permutation graph.
Comparability graphs were characterised by forbidden induced subgraphs in [9].
This characterization immediately leads to a forbidden induced subgraph
characterization for permutation graphs. By relying on the corresponding list
of forbidden subgraphs and the fact that $G$ is also a split graph, we
concluded that $G$ contains an induced subgraph $H$ isomorphic to one of the
graphs in Figure 1 (see [2]).

Figure 1: Forbidden induced subgraphs for permutation graphs within split
graphs.

Let us now consider an arbitrary split graph $G$ (either circle or not).
Because of the discussion in the preceding paragraph, if $G$ contains none of
the graphs in Figure 1 as an induced subgraph, then $G$ is a circle graph.
Thus, we assume next that $G$ contains an induced subgraph $H$ isomorphic to
tent, $4$-tent or co-$4$-tent. Let $(K,S)$ be a split partition of $G$. We
consider a partition $K_{1},\ldots,K_{j}$ of the vertices of $K$, where each
set $K_{i}$ consists of all the vertices of $K$ having a same set of
neighbours in $V(H)\cap S$. For each set $K_{i}$, let $S_{i}$ be the set of
vertices in $S$ that are adjacent to at least one vertex of $K_{i}$. We
consider the $(0,1)$-matrices $A(S_{i},K_{i})$ that represent the adjacencies
between $S_{i}$ and $K_{i}$. In [2], we show that it suffices to study each of
these matrices and the relationship between them to decide whether $G$ is a
circle graph or not. More precisely, the key condition for $G$ to be a circle
graph is that each of these matrices $A(S_{i},K_{i})$ is $2$-nested. This
analysis allowed us to give a minimal forbidden induced subgraph
characterization of those split graphs that are circle graphs [2].

This work is organized as follows. In Section 2 we give some basic definitions
and notation that will be useful thoughout this paper. In Section 3, we give a
motivating example and set the necessary bases to define $2$-nested matrices.
In Section 4, we characterise $2$-nested matrices by minimal forbidden
subconfigurations.

##  2 Basic definitions and notation

Let $A=(a_{ij})$ be a $n\times m$ $(0,1)$-matrix. We denote $a_{i.}$ and
$a_{.j}$ the $i$th row and the $j$th column of matrix $A$. From now on, we
associate each row $a_{i.}$ with the set of columns in which $a_{i.}$ has a
$1$. For example, the _intersection_ of two rows $a_{i.}$ and $a_{j.}$ is the
subset of columns in which both rows have a $1$. Two rows $a_{i.}$ and
$a_{k.}$ are _disjoint_ if there is no $j$ such that $a_{ij}=a_{kj}=1$. We say
that $a_{i.}$ is _contained_ in $a_{k.}$ if for each $j$ such that $a_{ij}=1$
also $a_{kj}=1$. We say that $a_{i.}$ and $a_{k.}$ are _nested_ if $a_{i.}$ is
contained in $a_{k.}$ or $a_{k.}$ is contained in $a_{i.}$. We say that a row
$a_{i.}$ is _empty_ if every entry of $a_{i.}$ is $0$, and we say that
$a_{i.}$ is _nonempty_ if there is at least one entry of $a_{i.}$ equal to
$1$. We say that two nonempty rows _overlap_ if they are non-disjoint and non-
nested. For every nonempty row $a_{i.}$, let
$l_{i}=\min\\{j\colon\,a_{ij}=1\\}$ and $r_{i}=\max\\{j\colon\,a_{ij}=1\\}$
for each $i\in\\{1,\ldots,n\\}$. Finally, we say that $a_{i.}$ and $a_{k.}$
_start_ (resp.  _end_) _in the same column_ if $l_{i}=l_{k}$ (resp.
$r_{i}=r_{k}$), and we say $a_{i.}$ and $a_{k.}$ _start (end) in different
columns_ , otherwise. The _complement_ of a row of a $(0,1)$-matrix arises by
turning all the $0$’s into $1$’s and vice versa. We denote the complement of a
row $r$ by $\overline{r}$.

All graphs in this work are simple, undirected, with no loops and no multiple
edges. We denote the vertex and edge set of a graph by $V(G)$ and $E(G)$,
respectively. A _clique_ is a set of pairwise adjacent vertices. A _stable
set_ is a set of pairwise nonadjacent vertices. Let $G$ be a graph. If
$W\subseteq V(G)$, the _subgraph of $G$ induced by $W$_, denoted $G[W]$, is
the graph with vertex set $W$ and whose edges are those of $G$ with both
endpoints in $W$. If $H$ is an induced subgraph of $G$, we denote by $G-H$ the
graph $G[V(G)-V(H)]$. We say a vertex $v$ is _complete to_ the set of vertices
$X$ if $v$ is adjacent to every vertex in $X$, and we say $v$ is _anticomplete
to_ $X$ if $v$ has no neighbour in $X$. We say that $v$ is _adjacent to_ $X$
if $v$ has at least one neighbour in $X$. If $v$ is a vertex of $G$, we denote
by $N(v)$ the set of vertices adjacent to $v$. Given two vertices $v_{1}$ and
$v_{2}$ in $S$, we say that $v_{1}$ and $v_{2}$ are _nested_ if either
$N(v_{1})\subseteq N(v_{2})$ or $N(v_{2})\subseteq N(v_{1})$. The _length_ of
a path or cycle is the number of edges of the path joining consecutive
vertices. A path or cycle is _odd_ or _even_ depending on whether its length
is odd or even, respectively. A path or cycle is _induced_ if there is no edge
joining two non-consecutive vertices. A _$2$ -coloring_ of $G$ is a mapping
that assigns one of two colors to each vertex of $G$. A $2$-coloring is
_proper_ if each two adjacent vertices are assigned different colors.

Let $G=(K,S)$ be a split graph. Let $s_{1},\ldots,s_{n}$ and
$v_{1},\ldots,v_{m}$ be linear orderings of $S$ and $K$, respectively. Let
$A=A(S,K)$ be the $n\times m$ matrix defined by $A(i,j)=1$ if $s_{i}$ is
adjacent to $v_{j}$ and $A(i,j)=0$, otherwise. From now on, we associate the
rows (resp. columns) of the adjacency matrix $A(S,K)$ with the corresponding
vertex in $S$ (resp. vertex in $K$). Given a partition
$K_{1},K_{2},\ldots,K_{j}$ of $K$ and a vertex $v$ in $S$, we denote
$N_{i}(v)=N(v)\cap K_{i}$.

##  3 Motivation: the connection between 2-nested matrices and circle graphs

In this section we first give motivating examples for the definition of nested
and $2$-nested matrices. Afterwards, we define nested and $2$-nested matrices,
which are of fundamental importance to describe a circle model for those split
graphs that are also circle, as we will see in the following examples.

Let us consider the split graph $G=(K,S)$ represented in Figure 2(a). Since
$G$ contains an tent $H$ induced by
$\\{k_{1},k_{3},k_{5},s_{13},s_{35},s_{51}\\}$, we consider the partitions
$K_{1},K_{2}\ldots,K_{6}$ of $K$ and $\\{S_{ij}\\}_{1\leq i,j\leq 6}$ of $S$,
defined as follows.

  * •

For each $i\in\\{1,3,5\\}$, let $K_{i}$ be the set of vertices of $K$ whose
neighbours in $V(H)\cap S$ are precisely $s_{(i-2)i}$ and $s_{i(i+2)}$ (where
subindexes are modulo $6$).

  * •

For each $i\in\\{2,4,6\\}$, let $K_{i}$ be the set of vertices of $K$ whose
only neighbour in $V(H)\cap S$ is $s_{(i-1)(i+1)}$ (where subindexes are
modulo $6$).

  * •

For $i,j\in\\{1,\ldots,6\\}$, let $S_{ij}$ be the set of vertices of $S$ that
are adjacent to some vertex in $K_{i}$ and some vertex in $K_{j}$, are
complete to $K_{i+1}$, $K_{i+2}$ ,$\ldots,K_{j-1}$, and are anticomplete to
$K_{j+1}$, $K_{j+2},\ldots,K_{i-1}$ (where subindexes are modulo $6$).

(a) A split circle graph $G$.

(b) A circle model for $G$.

Figure 2: Graph and circle model of Example $1$.

Notice that every vertex in $K\setminus V(H)$ lies in $K_{2}$, for the only
adjacency of these vertices with regard to $V(H)\cap S$ is the vertex
$s_{13}$. Thus, $K_{2}=\\{k_{21}$, $k_{22}$, $k_{23}$, $k_{24}\\}$. Moreover,
the orange vertices are precisely $S\setminus V(H)$ and these vertices are
adjacent only to vertices in $K_{2}$. Thus, they all lie in $S_{22}$. We want
to find properties that help us decide whether we can give a circle model for
$G$ or not. The tent graph admits a unique circle model in the sense that
circular ordering of the endpoints of the chords in the model is uniquely
determined. This is because the tent is prime with respect to the split
decomposition (see [3]). Hence, let us begin by considering a circle model for
$H$ as the one presented in Figure 3. We denote the arcs and chords of a model
by their endpoints in clockwise order. For example, in Figure 3 the arc
$k_{1}^{+}k_{3}^{+}$ is the portion of the circle that lies between $k_{1}$
and $k_{3}$ while traversing the circumference clockwise.

Figure 3: A circle model for the tent graph $H$.

In order to place the chords corresponding to each vertex in $S_{22}$, we need
to place first the chords that represent every vertex in $K_{2}$. Notice that
a chord representing a vertex in $K_{2}$ has one endpoint between the arc
$k_{1}^{+}k_{3}^{+}$ and the other endpoint between the arc
$s_{51}^{-}s_{35}^{+}$ while a chord representing a vertex in $S_{22}$ has
either both endpoints inside the arc $k_{1}^{+}k_{3}^{+}$ or both endpoints
inside the arc $s_{51}^{-}s_{35}^{+}$, always intersecting at least one chord
that represents a vertex of $K_{2}$. Thus, in order to place the chords
corresponding to the vertices of $K_{2}$ we need to establish a “good
ordering” for these vertices, this is, one that respects the relationships
among the neighbourhoods of the vertices in $S_{22}$. For example, since
$N(s_{1})\subseteq N(s_{2})$, it follows that an ordering of the chords in
$K_{2}$ that allows us to give a circle model must contain one of the
following four subsequences: $(k_{21}<k_{22}<k_{23})$,
$(k_{22}<k_{21}<k_{23})$, $(k_{23}<k_{21}<k_{22})$ or
$(k_{23}<k_{22}<k_{21})$. Moreover, since $N(s_{2})\cap N(s_{3})\neq\emptyset$
and $N(s_{2})$ and $N(s_{3})$ are not nested, then the chords corresponding to
$s_{2}$ and $s_{3}$ must be drawn in distinct portions of the circle model,
for they represent vertices in $S$ and thus the chords cannot intersect. The
vertex $s_{4}$ is adjacent only to $k_{21}$, thus $N(s_{4})$ is contained in
both $N(s_{1})$ and $N(s_{2})$ and is disjoint with $N(s_{3})$. Hence, the
chord that represents $s_{4}$ may be placed indistinctly in any of the two
portions of the circle corresponding to the partition $S_{22}$.

Therefore, when considering the placement of the chords, we find ourselves
facing two important decisions: (1) in which order should we place the chords
corresponding to the vertices in $K_{2}$ so that it is also possible to draw
the chords of those vertices in $S$ adjacent to $K_{2}$? and (2) in which
portion of the circle model should we place both endpoints of the chords
corresponding to vertices in $S_{22}$? We give a circle model for $G$ in
Figure 2(b)

Yet in this small example of a split graph that is circle, it becomes evident
that there is a property that must hold for every pair of vertices in $S$ that
have both of its endpoints placed within the same arc of the circumference.
This led to the definition of nested matrices below, which was the first step
towards expressing some of these problems regarding the placement of chords
for a circle model in terms of certain properties of the adjacency matrix
$A(S,K)$ (see Section 2 for the definition of $A(S,K)$).

######  Definition 3.1.

Let $A$ be a $(0,1)$-matrix. We say $A$ is _nested_ [15] if it has the
consecutive-ones property and every two rows are disjoint or nested.

######  Definition 3.2.

A split graph $G=(K,S)$ is _nested_ if and only if $A(S,K)$ is a nested
matrix.

$\small{\begin{pmatrix}110\cr 011\end{pmatrix}}$ Figure 4: The $0$-gem matrix

Nested matrices were characterised in [15] by a single forbidden matrix.

######  Theorem 3.3 ([15]).

A $(0,1)$-matrix is nested if and only if it contains no $0$-gem as a
submatrix up to permutations of rows and/or columns (see Figure 4)

Let us consider the matrix $A(S_{22},K_{2})$ corresponding to the graph $G$
given in Figure 2(a). In this case, the rows are given by $s_{1}$, $s_{2}$,
$s_{3}$ and $s_{4}$, and the columns are $k_{21}$, $k_{22}$, $k_{23}$ and
$k_{24}$.

$A(S_{22},K_{2})=\begin{pmatrix}1100\\\ 1110\\\ 0110\\\ 1000\end{pmatrix}$

Notice that the C$1$P for the matrix $A(S_{22},K_{2})$ is a necessary
condition to obtain an ordering of the vertices of $K_{2}$ that is compatible
with the partial ordering given by containment for the vertices in $S_{22}$.
Moreover, if the matrix $A(S_{22},K_{2})$ is nested, then any two vertices in
$S_{22}$ are either nested or disjoint. In other words, if $A(S_{22},K_{2})$
is nested, then we can draw every chord corresponding to a vertex in
$S\setminus V(H)$ in the same arc of the circumference. However, this is not
the case in the previous example, for the vertices $s_{1}$ and $s_{3}$ are
neither disjoint nor nested and thus they cannot be drawn in the same portion
of the circle model. Equivalently, $A(S,K)$ is not a nested matrix. Since we
have shown a circle model for $G$, it follows that the “nestedness” of
$A(S,K)$ is not enough to determine whether or not there is a circle model for
a given split graph $G=(K,S)$.

(a) A split circle graph $G^{\prime}$.

(b) A circle model for $G^{\prime}$.

Figure 5: Graph and circle model of Example $2$.

Let us see one more example. Consider $G^{\prime}$ to be the split graph
depicted in Figure 5(a). Notice that $G^{\prime}$ arises from $G$ by adding
three new vertices. Unlike what happens with the chords corresponding to
$s_{1}$, $s_{2}$, $s_{3}$ and $s_{4}$, the chords that represent the new
vertices $s_{5}$, $s_{6}$ and $s_{7}$ have only one of its endpoints in the
arcs corresponding to the area of the circle designated for $K_{2}$, this is,
in the arcs $k^{+}_{1}k^{+}_{3}$ and $s_{51}^{-}s_{35}^{+}$. Furthermore, each
of these new vertices has a unique possible placement for each endpoint of
their corresponding chord –meaning that there exists a unique arc of the
circumference in which we can place the endpoint. Let us consider
$S^{\prime}=S\setminus V(H)=\\{s_{1},\ldots,s_{7}\\}$. If we consider the rows
given by the vertices in $S^{\prime}$ and the columns given by
$k_{21},\ldots,k_{24}$, then the adjacency matrix $A(S^{\prime},K_{2})$ in
this example is as follows:

$A(S^{\prime},K_{2})=\scriptsize{\begin{pmatrix}1100\\\ 1110\\\ 0110\\\
1000\\\ 1110\\\ 1000\\\ 0111\end{pmatrix}}$

As in the previous example, $A(S^{\prime},K_{2})$ is not a nested matrix. Also
notice that $s_{5}$, $s_{6}$ and $s_{7}$ all are adjacent to at least one
vertex in $K\setminus K_{2}$. Let us concentrate in the placement of the
endpoints of the chords corresponding to $s_{5}$, $s_{6}$ and $s_{7}$ that lie
between the arcs $k_{1}k_{3}$ and $s_{51}s_{35}$. Notice that the “nested or
disjoint” property must still hold, and not only for those vertices in
$K_{2}$. More precisely, since $s_{5}$ is adjacent to $k_{24}$, $k_{23}$ and
$k_{1}$, while $s_{1}$ is nonadjacent to $k_{1}$ and adjacent to $k_{23}$ and
$k_{24}$, then necessarily $s_{1}$ must be contained in $s_{5}$. Something
similar occurs with $s_{7}$ and $s_{3}$, whereas $s_{6}$ and $s_{3}$ are
disjoint.

There is one situation in this example that did not occur in Example $1$.
Since $s_{6}$ is adjacent to $k_{21}$, $k_{1}$ and $k_{5}$, the chord
corresponding to the vertex $k_{21}$ is forced to be placed first within every
chord corresponding to $K_{2}$. This follows from the fact that a chord that
represents $s_{6}$ must have one of its endpoints placed inside the arc
$s_{51}^{-}s_{35}^{+}$, for we need $k_{21}$ to be the first chord of $K_{2}$
that comes right after $s_{51}$. Moreover, this is once again confirmed by the
fact that $s_{5}$ is adjacent to $k_{1}$ and $k_{21}$, thus the chord
corresponding to the vertex $k_{21}$ must be drawn first when considering the
ordering given by the neighbourhoods of those vertices in $S$ that have at
least one endpoint lying in $k_{1}^{+}k_{3}^{+}$. It follows that $k_{21}$
being the first vertex in the ordering is a necessary condition when searching
for a consecutive-ones ordering for the matrix $A(S^{\prime},K_{2})$. See
Figure 5(b), where we give a circle model for the graph $G^{\prime}$.

The previously described situations must also hold for each set $K_{i}$. For
each $K_{i}\subseteq K$, there are exactly two arcs of the circumference in
which we can place the endpoints of a chord corresponding to a vertex in
$K_{i}$. Moreover, since these vertices lie in $K$, such a chord must have
precisely one endpoint on each of these arcs. We denote these two arcs as
$K_{i}^{+}$ and $K_{i}^{-}$.

We translate the problem of giving a circle model to the fullfilment of some
properties for each of the matrices $A(S_{i},K_{i})$, where $\\{K_{i}\\}$ is a
partition of $K$ depending on some induced subgraph $H$ isomorphic to tent,
$4$-tent or co-$4$-tent, as described in the introduction. In order to express
the corresponding properties in matrix terms, we define enriched matrices.

######  Definition 3.4.

An _enriched matrix_ $A$ is a $(0,1)$-matrix together with an assignment of
labels and colors to some (possibly none) of its rows such that all the
following assertions hold:

  1. 1.

Each row of $A$ is either unlabeled or labeled with one of the following
labels: L or R or LR. We say that a row is an _LR-row (resp. L-row, R-row)_ if
it is labeled with LR (resp. L, R).

  2. 2.

Each row of $A$ is either uncolored or colored with either blue or red.

  3. 3.

The only rows that might be colored are those labeled with L or R, and those
empty LR-rows.

  4. 4.

All the empty LR-rows are colored with the same color.

The _underlying matrix of an enriched matrix $A$_ is the $(0,1)$-matrix with
the same entries as $A$ but that has neither labeled nor colored rows.

We denote the color assignment for a row with a colored bullet at the right
side of the row. The color assignment for some of the rows represents in which
arc of the circle corresponding to $K_{i}$ we must draw one or both endpoints
when considering the placement of the chords. Some of the vertices in $S$ have
a unique possible placement for the endpoints of its chords , and some of them
can _a priori_ be drawn in either two of the arcs $K_{i}^{+}$ and $K_{i}^{-}$.
Moreover, the labeling of the rows indicates “from which direction does the
chord come from” if we are standing in a particular portion of the circle. For
example, the following is the matrix $A(S^{\prime},K_{2})$ for the circle
model represented in Figure 5(b) turned into an enriched matrix by taking into
account all the information on the placement of the chords in the model:

$A(S^{\prime},K_{2})=\scriptsize{\bordermatrix{&\cr&1100\cr&1110\cr&0110\cr&1000\cr\textbf{L}&1110\cr\textbf{L}&1000\cr\textbf{R}&0111}\,\begin{matrix}\cr\cr\cr\cr{\color[rgb]{0.94140625,0.1953125,0.234375}\bullet}\cr{\color[rgb]{0,0,1}\bullet}\cr{\color[rgb]{0,0,1}\bullet}\end{matrix}}$

In this example, the rows of the enriched matrix are $s_{1},\ldots,s_{7}$, in
that order. Notice that $s_{5}$ is adjacent to $k_{1}\in K_{1}$ and some
vertices in $K_{2}$, thus $s_{5}$ lies in $S_{12}$. The chords of the vertices
in $S_{12}$ can only have its endpoints placed in the arcs
$s_{13}^{+}k_{1}^{+}$ and $k_{1}^{+}k_{3}^{+}$. More precisely, in terms of
intersecting the chords of $K_{2}$, those vertices in $S_{12}$ have one of its
endpoints placed in $K_{2}^{+}$. Something similar happens with the vertex
$s_{6}\in S_{52}$, whose endpoint intersecting chords of $K_{2}$ must be
placed somewhere in the arc $K_{2}^{-}$. Hence, we need to assign distinct
colors to this rows in order to denote in which of $K_{2}^{+}$ or $K_{2}^{-}$
we are able to draw the endpoint of the chord that should intersect its
neighbours in $K_{2}$. Furthermore, notice that both rows are labeled with L
in $A(S^{\prime},K)$. If we stand in $K_{2}^{+}$ and consider from which
direction should the chord corresponding to $s_{5}$ come from, then we notice
that it should come from the left. The same holds for $s_{6}$ if we stand in
$K_{2}^{-}$. On the other hand, the chord corresponding to $s_{7}$ should come
from the right, and this is why these three rows are labeled with L or R.

######  Definition 3.5.

Let $A$ be an enriched matrix. We say $A$ is _LR-orderable_ if there is a
linear ordering $\Pi$ for the columns of $A$ such that each of the following
assertions holds:

  * •

$\Pi$ is a consecutive-ones ordering for every non-LR-row of $A$.

  * •

The ordering $\Pi$ is such that the $1$’s in every nonempty row labeled with L
(resp. R) start in the first column (resp. end in the last column).

  * •

$\Pi$ is a consecutive-ones ordering for the complements of every LR-row of
$A$.

Such an ordering is called an _LR-ordering_. For each row of $A$ labeled with
L or LR and having a $1$ in the first column of $\Pi$, we define its _L-block
(with respect to $\Pi$)_ as the maximal set of consecutive columns of $\Pi$ on
which the row has a 1 starting in the first column. _R-blocks_ are defined on
an entirely analogous way. For each unlabeled row of $A$, we say its _U-block
(with respect to $\Pi$)_ is the set of columns having a $1$ in the row. The
blocks of $A$ with respect to $\Pi$ are its L-blocks, its R-blocks and its
U-blocks.

######  Definition 3.6.

Let $A$ be an enriched matrix with an LR-ordering. We say an _L-block (resp.
R-block, U-block) is colored_ if there is a color assignment for every entry
of the block.

A _basic bi-coloring for the blocks of $A$_ is a color assignment with either
red or blue for some L-blocks, U-blocks and R-blocks of $A$. A basic bi-
coloring is _total_ if every L-block, R-block and U-block of $A$ is colored,
and is _partial_ if otherwise.

Recall that, according to the definition, in an enriched matrix, the only rows
that might be colored are those labeled with L or R and those empty LR-rows.
Moreover, in an LR-ordering, every row labeled with L (resp. R) starts in the
first column (resp. ends in the last column), and the $1$’s in each row appear
consecutively. Thus, if an enriched matrix is also LR-orderable, then the
given coloring induces a partial basic bi-coloring (see Figure 6(a)) , in
which every empty LR-row remains unchanged, whereas for every nonempty colored
labeled row, we color all its $1$’s with the color given in the definition of
the matrix.

$\displaystyle
A=\scriptsize{\bordermatrix{&\cr\textbf{LR}&10001\cr\textbf{LR}&11001\cr&01100\cr\textbf{L}&{\color[rgb]{0.94140625,0.1953125,0.234375}1}{\color[rgb]{0.94140625,0.1953125,0.234375}1}{\color[rgb]{0.94140625,0.1953125,0.234375}1}00\cr\textbf{LR}&00000\cr\textbf{R}&00{\color[rgb]{0,0,1}1}{\color[rgb]{0,0,1}1}{\color[rgb]{0,0,1}1}}\,\begin{matrix}\cr\cr\cr{\color[rgb]{0.94140625,0.1953125,0.234375}\bullet}\cr{\color[rgb]{0,0,1}\bullet}\cr{\color[rgb]{0,0,1}\bullet}\end{matrix}}$
(a) An enriched LR-orderable matrix $A$.

$\displaystyle
A^{\prime}=\scriptsize{\bordermatrix{&\cr\textbf{LR}&{\color[rgb]{0,0,1}1}000{\color[rgb]{0.94140625,0.1953125,0.234375}1}\cr\textbf{LR}&{\color[rgb]{0,0,1}1}{\color[rgb]{0,0,1}1}00{\color[rgb]{0.94140625,0.1953125,0.234375}1}\cr&0{\color[rgb]{0.94140625,0.1953125,0.234375}1}{\color[rgb]{0.94140625,0.1953125,0.234375}1}00\cr\textbf{L}&{\color[rgb]{0.94140625,0.1953125,0.234375}1}{\color[rgb]{0.94140625,0.1953125,0.234375}1}{\color[rgb]{0.94140625,0.1953125,0.234375}1}00\cr\textbf{LR}&00000\cr\textbf{R}&00{\color[rgb]{0,0,1}1}{\color[rgb]{0,0,1}1}{\color[rgb]{0,0,1}1}}\,\begin{matrix}\\\
\\\ \\\ {\color[rgb]{0.94140625,0.1953125,0.234375}\bullet}\\\
{\color[rgb]{0,0,1}\bullet}\\\ {\color[rgb]{0,0,1}\bullet}\\\ \end{matrix}}$
(b) A total block bi-coloring of the blocks of $A$.

$\displaystyle
B=\scriptsize{\bordermatrix{&\cr\textbf{LR}&10101\cr\textbf{L}&{\color[rgb]{0.94140625,0.1953125,0.234375}1}{\color[rgb]{0.94140625,0.1953125,0.234375}1}000\cr\textbf{R}&000{\color[rgb]{0,0,1}1}{\color[rgb]{0,0,1}1}\cr&00110}\,\begin{matrix}\cr{\color[rgb]{0.94140625,0.1953125,0.234375}\bullet}\cr{\color[rgb]{0,0,1}\bullet}\cr\cr\end{matrix}}$
(c) An enriched non-LR-orderable matrix $B$.

Figure 6: Examples of enriched LR-orderable and non-LR-orderable matrices.

We now define $2$-nested matrices, which allow us to solve both the problem of
ordering the columns in each adjacency matrix $A(S_{i},K_{i})$ of a split
graph for each set $K_{i}$, and the problem of deciding if there is a feasible
distribution of the vertices in $S_{i}$ between the two arcs $K_{i}^{+}$ and
$K_{i}^{-}$. This allows to obtain a circle model for the given graph. We give
a complete characterization of $2$-nested matrices by forbidden
subconfigurations at the end of Section 4.

######  Definition 3.7.

Let $A$ be an enriched matrix. We say $A$ is _$2$ -nested_ if there exists an
LR-ordering $\Pi$ of $A$ and an assignment of colors red or blue to the blocks
of $A$ (with respect to $\Pi$) such that all of the following conditions hold:

  1. 1.

If an LR-row has an L-block and an R-block, then they are colored with
distinct colors.

  2. 2.

For each nonempty colored row $r$ in $A$, its only block is colored with the
same color as $r$ in $A$.

  3. 3.

If an L-block of an LR-row is properly contained in the L-block of an L-row,
then both blocks are colored with different colors.

  4. 4.

Every L-block of an LR-row and any R-block are disjoint. The same holds for an
R-block of an LR-row and any L-block.

  5. 5.

If an L-block and an R-block are not disjoint, then they are colored with
distinct colors.

  6. 6.

Each two U-blocks colored with the same color are either disjoint or nested.

  7. 7.

If an L-block and a U-block are colored with the same color, then either they
are disjoint or the U-block is contained in the L-block. The same holds
replacing L-block for R-block.

  8. 8.

If two distinct L-blocks of non-LR-rows are colored with distinct colors, then
every LR-row has an L-block. The same holds replacing L-block for R-block.

  9. 9.

If two LR-rows overlap, then the L-block of one and the R-block of the other
are colored with the same color.

An assignment of colors red and blue to the blocks of $A$ that satisfies all
these properties is called a _total block bi-coloring_.

######  Remark 1.

We now give some insight on what properties are behind each assertion in
Definition 3.7. All these properties are necessary conditions for each matrix
$A(S_{i},K_{i})$, in order to give a circle model for any split graph
containing a tent, $4$-tent or co-$4$-tent.

The LR-rows represent those independent vertices whose chords have its
endpoints placed inside distinct arcs corresponding to $K_{i}$. More
precisely, the difference between an LR-row and an unlabeled row, is that one
endpoint of the chord corresponding to an LR-row must be placed in $K_{i}^{+}$
and the other in $K_{i}^{-}$, whereas for an unlabeled row, either both
endpoints lie in $K_{i}^{+}$ or in $K_{i}^{-}$. Hence, assertion 1 of
Definition 3.7 ensures that, when deciding where to place the chord
corresponding to an LR-row, if the ordering indicates that the chord
intersects some of its adjacent vertices in one arc and the other in the other
arc, then the distinct blocks corresponding to the row must be colored with
distinct colors.

With assertion 2 of Definition 3.7, we ensure that the colors that are pre-
assigned remain unchanged, since they correspond to vertices in $S$ whose
chords admit a placement of the endpoint corresponding to $K_{i}$ in either
$K_{i}^{+}$ or $K_{i}^{-}$ and not in both indistinctly.

The third property refers to the ordering given by containment for the
vertices. In [2, 14], we see that every LR-row represents a vertex that is
adjacent to almost every vertex in the complete partition $K$ of $G$. Hence,
when dividing the LR-rows into blocks, we need to ensure that each of its
block is not properly contained in the neighbourhoods of vertices that are
nonadjacent to at least one partition of $K$. Something similar holds for
L-rows (resp. R-rows) and U-rows, and L-rows (resp. R-rows) and LR-rows. This
property is reflected in assertions 7 and 8.

Assertions 4, 5, 6 and 9 of the definition refer to the previously discussed
“nested or disjoint” property that we need to ensure in order to give a circle
model for $G$.

##  4 Characterization by forbidden subconfigurations

In this section, we begin giving some definitions that are necessary to state
Theorem 4.6, which is presented at the end of this section and is the main
result of this work. In Section 4.1 we define and characterise admissible
matrices, which give necessary conditions for a matrix to admit a total block
bi-coloring. In Section 4.2 we define and characterise LR-orderable and
partially $2$-nested matrices, and then we prove some properties of LR-
orderings in admissible matrices. Finally, in Section 4.3 we give the proof of
Theorem 4.6, which characterises $2$-nested matrices by forbidden
subconfigurations.

######  Definition 4.1.

Let $A$ and $B$ be enriched matrices. We say that _$B$ is a subconfiguration
of $A$_ if $B$ equals some submatrix of $A$ up to permutations of rows and/or
columns and such that the labels and colors remain the same. Given a subset of
rows $R$ (resp. of columns $C$) of $A$, we say that _$R$ (resp. $C$) induces a
matrix $B$_ if $B$ is a subconfiguration of the submatrix of $A$ formed by the
rows in $R$ (resp. the columns in $C$).

Let $\mathcal{F}$ be a family of enriched matrices. We say that $A$ is
$\mathcal{F}$-free if $A$ contains no $F$ as a subconfiguration, for every
$F\in\mathcal{F}$.

The $0$-gem, $1$-gem and $2$-gem are the following enriched matrices:

$\scriptsize{\begin{pmatrix}110\cr
011\end{pmatrix},\qquad\bordermatrix{&\cr&10\cr&11}\
,\qquad\bordermatrix{&\cr\textbf{LR}&110\cr\textbf{LR}&101}\ }$

respectively.

######  Definition 4.2.

Let $A$ be an enriched matrix. We say that $A$ _contains a gem_ (resp.
_doubly-weak gem_) if it contains a $0$-gem (resp. a $2$-gem) as a
subconfiguration. We say that $A$ _contains a weak gem_ if it contains a
$1$-gem such that, either the first corresponds to an L-row (resp. R-row) of
$A$ and the second corresponds to a U-row of $A$, or the first corresponds to
an LR-row of $A$ and the second corresponds to a non-LR-row of $A$. We say
that a $2$-gem is _badly-colored_ if the entries in the corresponding column
of $A$ in which both rows have a $1$ are in blocks colored with the same
color.

######  Definition 4.3.

Let $A$ be an enriched matrix. The dual matrix of $A$ is defined as the
enriched matrix $\tilde{A}$ that has the same underlying matrix as $A$ and for
which every row of $A$ that is labeled with L (resp. R) is now labeled with R
(resp. L) and every other row remains the same. Also, the color or lack of
color assignment of each row remains as in $A$.

In Figures 8, 9, 10, 11 and 12 we define some special matrices that play an
important role in the sequel. We will use green and orange to represent either
red and blue or blue and red, respectively. For every enriched matrix
represented in the figures of this section, if a row labeled with L or R
appears in black, then it may be colored with either red or blue indistinctly.
Also, if a row is labeled with “L (LR)” (resp. “R (LR)”), then such a row is a
row labeled with either L or LR (resp. R or LR) indistinctly and independently
from one another.

$\displaystyle M_{0}=\scriptsize{\bordermatrix{&\cr&1011\cr&1110\cr&0111}\ }$
$\displaystyle
M_{II}(4)=\scriptsize{\bordermatrix{&\cr&0111\cr&1100\cr&0110\cr&1101}\ }$
$\displaystyle
M_{V}=\scriptsize{\bordermatrix{&\cr&11000\cr&00110\cr&11110\cr&10011}\ }$
$\displaystyle S_{0}(k)$ $\displaystyle=\scriptsize{\begin{pmatrix}111...11\\\
110...00\\\ 011...00\\\ .....\\\ .....\\\ .....\\\ 000...11\\\ 100...01\\\
\end{pmatrix}}$ Figure 7: The matrices $M_{0}$, $M_{II}(4)$, $M_{V}$ and
$S_{0}(k)\in\\{0,1\\}^{((k+1)\times k}$ for any even $k\geq 4$. Figure 8: The
family of enriched matrices $\mathcal{D}$.

$\displaystyle F_{0}=\scriptsize{\begin{pmatrix}11100\\\ 01110\\\ 00111\\\
\end{pmatrix}}$ $\displaystyle
F_{1}(k)=\scriptsize{\begin{pmatrix}011...111\\\ 111...110\\\ 000...011\\\
000...110\\\ .....\\\ .....\\\ .....\\\ 110...000\\\ \end{pmatrix}}$
$\displaystyle F_{2}(k)=\scriptsize{\begin{pmatrix}0111...10\\\ 1100...00\\\
0110...00\\\ .....\\\ .....\\\ .....\\\ 0000...11\\\ \end{pmatrix}}$
$\displaystyle F^{\prime}_{0}=\scriptsize{\bordermatrix{&\cr\textbf{L
(LR)}&1100\cr&1110\cr&0111}\ }$

$\displaystyle
F^{\prime\prime}_{0}=\scriptsize{\bordermatrix{&\cr\textbf{L}&110\cr&111\cr\textbf{R}&011}\
}$ $\displaystyle F^{\prime}_{1}(k)=\scriptsize{\bordermatrix{&\cr&11\ldots
1111\cr\textbf{L (LR)}&11\ldots 1110\cr&00\ldots 0011\cr&00\ldots
0110\cr&\iddots\cr\textbf{L (LR)}&10\ldots 0000}\ }$ $\displaystyle
F^{\prime}_{2}(k)=\scriptsize{\bordermatrix{&\cr&111\ldots 10\cr\textbf{L
(LR)}&100\ldots 00\cr&110\ldots 00\cr&\ddots\cr&000\ldots 11}\ }$

Figure 9: The enriched matrices of the family $\mathcal{F}$.

The matrices $\mathcal{F}$ represented in Figure 9 are defined as follows:
$F_{1}(k)\in\\{0,1\\}^{k\times(k-1)}$, $F_{2}(k)\in\\{0,1\\}^{k\times k}$,
$F^{\prime}_{1}(k)\in\\{0,1\\}^{k\times(k-2)}$ and
$F^{\prime}_{2}(k)\in\\{0,1\\}^{k\times(k-1)}$, for every odd $k\geq 5$. In
the case of $F^{\prime}_{0}$, $F^{\prime}_{1}(k)$ and $F^{\prime}_{2}(k)$, the
labeled rows may be either L or LR indistinctly and independently from one
another, and in the case of their dual matrices, the labeled rows may be
either R or LR indistinctly and independently from one another.

The matrices $\mathcal{S}$ in Figure 10 are defined as follows. If $k$ is odd,
then $S_{1}(k)\in\\{0,1\\}^{(k+1)\times k}$ for $k\geq 3$, and if $k$ is even,
then $S_{1}(k)\in\\{0,1\\}^{k\times(k-2)}$ for $k\geq 4$. The remaining
matrices have the same size whether $k$ is even or odd:
$S_{2}(k)\in\\{0,1\\}^{k\times(k-1)}$ for $k\geq 3$,
$S_{3}(k)\in\\{0,1\\}^{k\times(k-1)}$ for $k\geq 3$,
$S_{5}(k)\in\\{0,1\\}^{k\times(k-2)}$ for $k\geq 4$,
$S_{4}(k)\in\\{0,1\\}^{k\times(k-1)}$, $S_{6}(k)\in\\{0,1\\}^{k\times k}$ for
$k\geq 4$, $S_{7}(k)\in\\{0,1\\}^{k\times(k+1)}$ for every $k\geq 3$ and
$S_{8}(2j)\in\\{0,1\\}^{2j\times(2j)}$ for $j\geq 2$. If $k$ is even, then the
first and last row of $S_{2}(k)$ and $S_{3}(k)$ are colored with the same
color, whereas in $S_{4}(k)$ and $S_{5}(k)$ are colored with distinct colors.

$\displaystyle S_{1}(2j)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{L}&10\ldots
00\cr&11\ldots 00\cr&\ddots\cr&00\ldots 11\cr\textbf{LR}&00\ldots
01\cr\textbf{L}&11\ldots 11}\ }$ $\displaystyle S_{1}(2j+1)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{L}&10\ldots
00\cr&11\ldots 00\cr&\ddots\cr&00\ldots 11\cr\textbf{LR}&00\ldots 01}\ }$
$\displaystyle S_{2}(k)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{L}&10\ldots
00\cr&11\ldots 00\cr&\ddots\cr&00\ldots 11\cr\textbf{L}&11\ldots 10}\
\begin{matrix}{\color[rgb]{1,0.578125,0.08984375}\bullet}\\\ \\\ \\\ \\\ \\\
{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\ \end{matrix}}$

$\displaystyle S_{3}(k)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{L}&10\ldots
00\cr&11\ldots 00\cr&\ddots\cr&00\ldots 11\cr\textbf{R}&00\ldots 01}\
\begin{matrix}{\color[rgb]{1,0.578125,0.08984375}\bullet}\\\ \\\ \\\ \\\ \\\
{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\ \end{matrix}}$
$\displaystyle S_{4}(k)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{LR}&11\ldots
11\cr\textbf{L}&10\ldots 00\cr&11\ldots 00\cr&\ddots\cr&00\ldots
11\cr\textbf{R}&00\ldots 01}\ \begin{matrix}\\\
{\color[rgb]{1,0.578125,0.08984375}\bullet}\\\ \\\ \\\ \\\ \\\
{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\ \end{matrix}}$
$\displaystyle S_{5}(k)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{L}&10\ldots
00\cr&11\ldots 00\cr&\ddots\cr&00\ldots 11\cr\textbf{LR}&11\ldots
10\cr\textbf{L}&11\ldots 11}\
\begin{matrix}{\color[rgb]{1,0.578125,0.08984375}\bullet}\\\ \\\ \\\ \\\ \\\
\\\ {\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\ \end{matrix}}$

$\displaystyle S_{6}(3)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{LR}&110\cr\textbf{R}&011\cr&110}\
}$ $\displaystyle S_{6}^{\prime}(3)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{LR}&110\cr\textbf{R}&011\cr&111}\
}$ $\displaystyle S_{6}(k)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{LR}&111\ldots
110\cr\textbf{R}&011\ldots 111\cr&110\ldots 000\cr&\ddots\cr&000\ldots 011}\
\begin{matrix}\\\ \\\ {\color[rgb]{1,0.578125,0.08984375}\bullet}\\\ \\\ \\\
\\\ \\\ \\\ \end{matrix}}$

$\displaystyle S_{7}(3)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{LR}&11001\cr\textbf{LR}&10011\cr&11100}\
}$ $\displaystyle S_{7}(2j)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{LR}&1100\ldots
000\cr\textbf{LR}&1000\ldots 001\cr&0110\ldots 000\cr&\ddots\cr&0000\ldots
011}\ }$ $\displaystyle S_{8}(2j)$
$\displaystyle=\scriptsize{\bordermatrix{&\cr\textbf{LR}&100\ldots
001\cr&110\ldots 000\cr&\ddots\cr&000\ldots 011}\ }$

Figure 10: The family of matrices $\mathcal{S}$ for every $j\geq 2$ and every
odd $k\geq 3$

In the matrices $\mathcal{P}$, the integer $l$ represents the number of
unlabeled rows between the first row and the first LR-row. The matrices
$\mathcal{P}$ described in Figure 11 are defined as follow:
$P_{0}(k,0)\in\\{0,1\\}^{k\times k}$ for every $k\geq 4$,
$P_{0}(k,l)\in\\{0,1\\}^{k\times(k-1)}$ for every $k\geq 5$ and $l>0$;
$P_{1}(k,0)\in\\{0,1\\}^{k\times(k-1)}$ for every $k\geq 5$,
$P_{1}(k,l)\in\\{0,1\\}^{k\times(k-2)}$ for every $k\geq 6$, $l>0$;
$P_{2}(k,0)\in\\{0,1\\}^{k\times(k-1)}$ for every $k\geq 7$,
$P_{2}(k,l)\in\\{0,1\\}^{k\times(k-2)}$ for every $k\geq 8$ and $l>0$. If $k$
is even, then the first and last row of every matrix in $\mathcal{P}$ are
colored with distinct colors.

$\displaystyle P_{0}(k,0)=\scriptsize{\bordermatrix{&\cr\textbf{L}&11000\ldots
000\cr\textbf{LR}&10011\ldots 111\cr&00110\ldots 000\cr&\ddots\cr&00000\ldots
011\cr\textbf{R}&00000\ldots 001}\
\begin{matrix}{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\ \\\ \\\
\\\ \\\ \\\
{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\end{matrix}}$
$\displaystyle P_{0}(k,l)=\scriptsize{\bordermatrix{&\cr\textbf{L}&100\ldots
0000\ldots 0\cr&110\ldots 0000\ldots 0\cr&\ddots\cr&000\ldots 1100\ldots
0\cr\textbf{LR}&111\ldots 1001\ldots 1\cr&000\ldots 0011\ldots
0\cr&\ddots\cr&000\ldots 00\ldots 011\cr\textbf{R}&000\ldots 00\ldots 001}\
\begin{matrix}{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\ \\\ \\\
\\\ \\\ \\\ \\\ \\\ \\\ \\\
{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\end{matrix}}$

$\displaystyle P_{1}(k,0)=\scriptsize{\bordermatrix{&\cr\textbf{L}&1100\ldots
000\cr\textbf{LR}&1011\ldots 111\cr\textbf{LR}&1101\ldots 111\cr&00110\ldots
000\cr&\ddots\cr&00000\ldots 011\cr\textbf{R}&0000\ldots 001}\
\begin{matrix}{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\ \\\ \\\
\\\ \\\ \\\ \\\
{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\end{matrix}}$
$\displaystyle P_{1}(k,l)=\scriptsize{\bordermatrix{&\cr\textbf{L}&100\ldots
0000\ldots 0\cr&110\ldots 0000\ldots 0\cr&\ddots\cr&000\ldots 1100\ldots
0\cr\textbf{LR}&111\ldots 1011\ldots 1\cr\textbf{LR}&111\ldots 1101\ldots
1\cr&000\ldots 0011\ldots 0\cr&\ddots\cr&000\ldots 00\ldots
011\cr\textbf{R}&000\ldots 00\ldots 001}\
\begin{matrix}{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\ \\\ \\\
\\\ \\\ \\\ \\\ \\\ \\\ \\\ \\\
{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\end{matrix}}$

$\displaystyle
P_{2}(k,0)=\scriptsize{\bordermatrix{&\cr\textbf{L}&110000\ldots
000\cr\textbf{LR}&101111\ldots 111\cr\textbf{LR}&111011\ldots
111\cr\textbf{LR}&110111\ldots 111\cr\textbf{LR}&111001\ldots
111\cr&000011\ldots 000\cr&\ddots\cr&00000\ldots 011\cr\textbf{R}&00000\ldots
001}\ \begin{matrix}{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\
\\\ \\\ \\\ \\\ \\\ \\\ \\\ \\\ \\\
{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\end{matrix}}$
$\displaystyle P_{2}(k,l)=\scriptsize{\bordermatrix{&\cr\textbf{L}&100\ldots
00000\ldots 0\cr&110\ldots 00000\ldots 0\cr&\ddots\cr&000\ldots 11000\ldots
0\cr\textbf{LR}&111\ldots 10011\ldots 1\cr\textbf{LR}&111\ldots 11101\ldots
1\cr\textbf{LR}&111\ldots 11011\ldots 1\cr\textbf{LR}&111\ldots 11001\ldots
1\cr&000\ldots 00011\ldots 0\cr&\ddots\cr&000\ldots 000\ldots
011\cr\textbf{R}&000\ldots 000\ldots 001}\
\begin{matrix}{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\\\ \\\ \\\
\\\ \\\ \\\ \\\ \\\ \ \\\ \\\ \\\ \\\ \\\ \\\
{\color[rgb]{0.25390625,0.6796875,0.22265625}\bullet}\end{matrix}}$

Figure 11: The family of enriched matrices $\mathcal{P}$ for every odd $k$.

$\displaystyle M_{2}^{\prime}(k)=\scriptsize{\bordermatrix{&\cr&111\ldots
111\cr\textbf{L}&100\ldots 000\cr&110\ldots 000\cr&\ddots\cr&000\ldots
110\cr\textbf{L}&111\ldots 101}\ }$ $\displaystyle
M_{2}^{\prime\prime}(k)=\scriptsize{\bordermatrix{&\cr\textbf{R}&111\ldots
111\cr\textbf{L}&100\ldots 000\cr&110\ldots 000\cr&\ddots\cr&000\ldots
110\cr\textbf{R}&000\ldots 010\cr\textbf{L}&111\ldots 111}\ }$

$\displaystyle
M_{3}^{\prime}(k)=\scriptsize{\bordermatrix{&\cr\textbf{L}&100\ldots
000\cr&110\ldots 000\cr&\ddots\cr&000\ldots 110\cr&111\ldots 101}\ }$
$\displaystyle
M_{3}^{\prime\prime}(k)=\scriptsize{\bordermatrix{&\cr&110\ldots
00\cr&011\ldots 00\cr&\ddots\cr&000\ldots 11\cr\textbf{R}&011\ldots 10}\ }$
$\displaystyle
M_{4}^{\prime}=\scriptsize{\bordermatrix{&\cr\textbf{L}&10000\cr&01100\cr&00011\cr&10101}\
}$

$\displaystyle
M_{4}^{\prime\prime}=\scriptsize{\bordermatrix{&\cr\textbf{L}&1000\cr\textbf{R}&0100\cr&0011\cr&1101}\
}$ $\displaystyle
M_{5}^{\prime}=\scriptsize{\bordermatrix{&\cr&1100\cr&0011\cr\textbf{R}&1001\cr&111}\
}$ $\displaystyle
M_{5}^{\prime\prime}=\scriptsize{\bordermatrix{&\cr\textbf{L}&1000\cr&0110\cr&1011\cr\textbf{L}&1110}\
}$

Figure 12: The enriched matrices in family $\mathcal{M}$: $M_{2}^{\prime}(k)$,
$M_{3}^{\prime}(k)$, $M_{3}^{\prime\prime}(k)$,
$M_{3}^{\prime\prime\prime}(k)$ for $k\geq 4$, and $M_{2}^{\prime\prime}(k)$
for $k\geq 5$.

######  Definition 4.4.

Let $A$ be an enriched matrix and let $\Pi$ be a LR-ordering. We define
$A^{*}$ as the enriched matrix that arises from $A$ by:

  * •

replacing each LR-row by its complement, and

  * •

adding two distinguished rows: one labeled with L and the other labeled with
R, and both of them having a $1$ in every column.

In [18], Tucker characterised all the minimal forbidden submatrices for the
C$1$P, later known as _Tucker matrices_.

######  Theorem 4.5.

The $(0,1)$–matrix $M$ has the consecutive-ones property for columns and rows
if and only if no submatrix of $M$, or of the transpose of $M$, is a member of
the families depicted in Figure 13.

$\displaystyle M_{I}(k)$ $\displaystyle=\scriptsize{\begin{pmatrix}110...00\\\
011...00\\\ .....\\\ .....\\\ .....\\\ 000...11\\\ 100...01\\\ \end{pmatrix}}$
$\displaystyle M_{II}(k)$
$\displaystyle=\scriptsize{\begin{pmatrix}011...111\\\ 110...000\\\
011...000\\\ .....\\\ .....\\\ 000...110\\\ 111...101\\\ \end{pmatrix}}$
$\displaystyle M_{III}(k)$
$\displaystyle=\scriptsize{\begin{pmatrix}110...000\\\ 011...000\\\ .....\\\
.....\\\ 000...110\\\ 011...101\\\ \end{pmatrix}}$

$\displaystyle M_{IV}$ $\displaystyle=\scriptsize{\begin{pmatrix}110000\\\
001100\\\ 000011\\\ 010101\\\ \end{pmatrix}}$ $\displaystyle M_{V}$
$\displaystyle=\scriptsize{\begin{pmatrix}11000\\\ 00110\\\ 11110\\\ 10011\\\
\end{pmatrix}}$

Figure 13: Tucker matrices $M_{I}(k)\in\\{0,1\\}^{k\times k}$,
$M_{III}(k)\in\\{0,1\\}^{k\times(k+1)}$ with $k\geq 3$, and
$M_{II}(k)\in\\{0,1\\}^{k\times k}$ with $k\geq 4$

Now we can state Theorem 4.6, which characterises $2$-nested matrices by
forbidden subconfigurations and is the main result of this work. The proof for
this theorem will be given at the end of the section.

######  Theorem 4.6.

Let $A$ be an enriched matrix. Then, $A$ is $2$-nested if and only if $A$
contains none of the following listed matrices or their dual matrices as
subconfigurations:

  * •

$M_{0}$, $M_{II}(4)$, $M_{V}$ or $S_{0}(k)$ for every even $k$ (see Figure 7)

  * •

every enriched matrix in the family $\mathcal{D}$ (see Figure 8)

  * •

every enriched matrix in the family $\mathcal{F}$ (see Figure 9)

  * •

every enriched matrix in the family $\mathcal{S}$ (see Figure 10)

  * •

every enriched matrix in the family $\mathcal{P}$ (see Figure 11)

  * •

monochromatic gems, monochromatic weak gems, badly-colored doubly-weak gems

and $A^{*}$ contains no Tucker matrices (see Figure 13) and none of the
enriched matrices in $\mathcal{M}$ or their dual matrices as subconfigurations
(see Figure 12).

Throughout the following sections we give some definitions and
characterizations that will allow us to prove the above theorem. In Section
4.1 we define and characterise the notion of admissibility, which encompasses
all the properties we need to consider when coloring the blocks of an enriched
matrix. In Section 4.2, we give a characterization for LR-orderable matrices
by forbidden subconfigurations. Afterwards, we define and characterise
partially $2$-nested matrices, which are those enriched matrices that admit an
LR-ordering and for which the given coloring of those labeled rows induces a
partial block bi-coloring. These definitions and characterizations allow us to
prove Lemmas 4.23 and 4.25, which are of fundamental importance for the proof
of Theorem 4.6.

###  4.1 Admissibility

In this section we define the notion of admissibility for an enriched
$(0,1)$-matrix, which allows us to describe the necessary conditions for an
enriched matrix to admit a block bi-coloring. Notice that the existence of a
block bi-coloring for an enriched matrix is a property that can be defined and
characterised by forbidden subconfigurations.

Let us consider the matrices defined in 8. These matrices are all examples of
enriched matrices that do not admit a total block bi-coloring (recall
Definition 3.7). For example, let us consider $D_{0}$. In order to have a
total block bi-coloring of $D_{0}$, it is necessary that $D_{0}$ admits an LR-
ordering of its columns. In particular, in such an ordering every row labeled
with L starts in the first column. Hence, if there is indeed an LR-ordering
for $D_{0}$, then the existence of two distinct non-nested rows labeled with L
is not possible. The same holds if both rows are labeled with R. We can use
similar arguments to see that neither $D_{2}$, $D_{3}$, $D_{7}$ and $D_{11}$
admit an LR-ordering and thus they do not admit a total block bi-coloring.

If instead we consider the enriched matrix $D_{1}$, then it is straightforward
to see that assertion 5 of Definition 3.7 does not hold for this matrix.
Consider now the matrix $D_{4}$. It follows from assertion 8 of Definition 3.7
that if an enriched matrix has two distinct rows labeled with L and colored
with distinct colors, then every LR-row has an L-block, and thus $D_{4}$ does
not admit a total block bi-coloring. Suppose now that $D_{4}$ is a submatrix
of some enriched matrix and that the corresponding LR-row is nonempty in $A$.
Notice that, if the LR-row has an L-block then it is properly contained in
both rows labeled with L. It follows from this and assertion 3 of Definition
3.7 that the L-block of the LR-row must be colored with a distinct color than
the one given to each row labeled with L. However, each of these rows is
colored with a distinct color, thus a total block bi-coloring is not possible
in that case. If we consider the enriched matrix $D_{5}$, then it follows from
assertion 4 of Definition 3.7 that there is no possible LR-ordering such that
the L-block of the LR-row does not intersect the L-row, and the same follows
for the R-block of the LR-row and the R-row of $D_{5}$.

Let us consider the enriched matrix in which we find $D_{6}$ as a
subconfiguration. If the LR-row has an L-block, then it is contained in the
L-row, and the same holds for the R-block of the LR-row and the R-row. By
assertion 3 of Definition 3.7, the L-block must be colored with a distinct
color than the L-row, and the R-block must be colored with a distinct color
than the R-row. Equivalently, the L-block and the R-block of the LR-row are
colored with the same color. However, this is not possible by assertion 1 of
Definition 3.7. Similarly, we can see that $D_{8}$, $D_{9}$, $D_{10}$,
$D_{12}$ and $D_{13}$ do not admit a total block bi-coloring, also having in
mind that assertion 9 of Definition 3.7 must hold pairwise for LR-rows.

######  Definition 4.7.

Let $A$ be an enriched matrix. We define the following properties:

  1. (a)

If two rows are labeled both with L or both with R, then they are nested.

  2. (b)

If two rows with the same color are labeled one with L and the other with R,
then they are disjoint.

  3. (c)

If two rows with distinct colors are labeled one with L and the other with R,
then either they are disjoint or there is no column where both have $0$
entries.

  4. (d)

If two rows $r_{1}$ and $r_{2}$ have distinct colors and are labeled one with
L and the other with R, then any LR-row with at least one non-zero column has
nonempty intersection with either $r_{1}$ or $r_{2}$.

  5. (e)

If two rows $r_{1}$ and $r_{2}$ with distinct colors are labeled both with L
or both with R, then for any LR-row $r$, $r_{1}$ is contained in $r$ or
$r_{2}$ is contained in $r$.

  6. (f)

If two non-disjoint rows $r_{1}$ and $r_{2}$ with distinct colors, one labeled
with L and the other labeled with R, then any LR-row is disjoint with regard
to the intersection of $r_{1}$ and $r_{2}$.

  7. (g)

If two rows with the same color are labeled one with L and the other with R,
then for any LR-row $r$ one of them is contained in $r$. Moreover, the same
holds for any two rows with distinct colors and labeled with the same letter.

  8. (h)

For each three non-disjoint rows such that two of them are LR-rows and the
other is labeled with either L or R, two of them are nested.

  9. (i)

If two rows $r_{1}$ and $r_{2}$ with distinct colors are labeled one with L
and the other with R, and there are two LR-rows $r_{3}$ and $r_{4}$ such that
$r_{1}$ is neither disjoint or contained in $r_{3}$ and $r_{2}$ is neither
disjoint or contained in $r_{4}$, then $r_{3}$ is nested in $r_{4}$ or
viceversa.

  10. (j)

For each three LR-rows, two of them are nested.

For each of the above properties, we characterise the set of minimal forbidden
subconfigurations with the following Lemma.

######  Lemma 4.8.

For any enriched matrix $A$, all of the following assertions hold:

  1. 1.

$A$ satisfies assertion (a) of Definition 4.7 if and only if $A$ contains no
$D_{0}$ or its dual matrix as a subconfiguration.

  2. 2.

$A$ satisfies assertion (b) of Definition 4.7 if and only if $A$ contains no
$D_{1}$ or its dual matrix as a subconfiguration.

  3. 3.

$A$ satisfies assertion (c) of Definition 4.7 if and only if $A$ contains no
$D_{2}$ or its dual matrix as a subconfiguration.

  4. 4.

$A$ satisfies assertion (d) of Definition 4.7 if and only if $A$ contains no
$D_{2}$, $D_{3}$ or their dual matrices as subconfigurations.

  5. 5.

$A$ satisfies assertion (e) of Definition 4.7 if and only if $A$ contains no
$D_{0}$, $D_{4}$ or their dual matrices as subconfigurations.

  6. 6.

$A$ satisfies assertion (f) of Definition 4.7 if and only if $A$ contains no
$D_{5}$ or its dual matrix as a subconfiguration.

  7. 7.

$A$ satisfies assertion (g) of Definition 4.7 if and only if $A$ contains no
$D_{0}$, $D_{1}$, $D_{4}$, $D_{6}$ or their dual matrices as
subconfigurations.

  8. 8.

$A$ satisfies assertion (h) of Definition 4.7 if and only if $A$ contains no
$D_{7}$, $D_{8}$, $D_{9}$ or their dual matrices as subconfigurations.

  9. 9.

$A$ satisfies assertion (i) of Definition 4.7 if and only if $A$ contains no
$D_{5}$, $D_{9}$, $D_{10}$ or its dual matrix as a subconfiguration.

  10. 10.

$A$ satisfies assertion (j) of Definition 4.7 if and only if $A$ contains no
$D_{11}$, $D_{12}$, $D_{13}$ or their dual matrices as subconfigurations.

###### Proof.

First we find every forbidden subconfiguration corresponding to assertion a of
Definition 4.7. Let $f_{1}$ and $f_{2}$ be two rows labeled both with L or
both with R, and suppose they are not nested. Thus, there is a column in which
$f_{1}$ has a $1$ and $f_{2}$ has a $0$, and another column in which $f_{2}$
has a $1$ and $f_{1}$ has a $0$. In this way, we find $D_{0}$ or its dual as a
subconfiguration of $A$.

Let us find now every forbidden subconfiguration corresponding to assertion b
of Definition 4.7. Let $f_{1}$ and $f_{2}$ be rows labeled one with L and the
other with R and colored with the same color. If $f_{1}$ and $f_{2}$ are not
disjoint, then there is a column in which both rows have a $1$. In this case,
we find $D_{1}$ or its dual as a subconfiguration of $A$.

For assertion c of Definition 4.7, let $f_{1}$ and $f_{2}$ be two rows labeled
one with L and the other with R and colored with distinct colors, and suppose
they are not disjoint and there is a column $j_{1}$ such that both rows have a
$0$ in column $j_{1}$. Thus, there is a column $j_{2}\neq j_{1}$ such that
both rows have a $1$ in column $j_{2}$. Hence, $D_{2}$ is a subconfiguration
of $A$.

With regard to assertion d of Definition 4.7, let $f_{1}$ and $f_{2}$ be two
rows labeled one with L and the other with R and colored with distinct colors.
Let $f_{3}$ be a nonempty LR-row. Suppose that $f_{3}$ is disjoint with both
$f_{1}$ and $f_{2}$. Hence, there is a column $l_{1}$ such that $f_{1}$ and
$f_{2}$ have a $0$ and $f_{3}$ has a $1$. Moreover, either there are two
distinct columns $j_{1}$ and $j_{2}$ such that the column $j_{i}$ has a $1$ in
row $f_{i}$ and a $0$ in the other rows, for $i=1,2$, or there is a column
$l_{2}$ such that $f_{1}$ and $f_{2}$ both have a $1$ in column $l_{2}$ and
$f_{3}$ has a $0$. If the latter holds, we find $D_{2}$ as a subconfiguration
induced by the rows $f_{1}$ and $f_{2}$. If instead there are two distinct
columns $j_{1}$ and $j_{2}$ as described above, then we find $D_{3}$ as a
subconfiguration of $A$.

For assertion e of Definition 4.7, let $f_{1}$ and $f_{2}$ be two rows labeled
with L and colored with distinct colors, and let $r$ be an LR-row. If $f_{1}$
and $f_{2}$ are not nested, then we find $D_{0}$ as a subconfiguration.
Suppose that $f_{1}$ and $f_{2}$ are nested. If neither $f_{1}$ nor $f_{2}$ is
contained in $r$, then there is a column $j$ in which $f_{1}$ and $f_{2}$ have
a $1$ and $r$ has a $0$. Thus, $D_{4}$ is a subconfiguration of $A$.

For assertion f of Definition 4.7, let $f_{1}$ and $f_{2}$ be two non-disjoint
rows colored with distinct colors, $f_{1}$ labeled with L and $f_{2}$ labeled
with R. Since they are non-disjoint, there is at least one column $j$ in which
both rows have a $1$. Suppose that for every such column $j$, there is an LR-
row $f$ having a $1$ in that column. Then, we find $D_{5}$ as a
subconfiguration of $A$.

For assertion g of Definition 4.7, let $f$ be an LR-row and let $f_{1}$ and
$f_{2}$ be two rows labeled with L and R respectively, and colored with the
same color. If $f_{1}$ and $f_{2}$ are not disjoint, then we find $D_{1}$ as a
subconfiguration. Suppose that $f_{1}$ and $f_{2}$ are disjoint. If neither
$f_{1}$ nor $f_{2}$ is contained in $f$, then there are columns $j_{1}\neq
j_{2}$ such that $f_{i}$ has a $1$ and $f$ has a $0$, for $i=1,2$. Thus, we
find $D_{6}$ as a subconfiguration of $A$. If instead $f_{1}$ and $f_{2}$ are
both labeled with L and colored with distinct colors, and neither is contained
in $f$, then we find $D_{4}$ or $D_{0}$ as a subconfiguration in $A$ depending
on whether or not $f_{1}$ and $f_{2}$ are nested.

Suppose that $A$ satisfies assertion h of Definition 4.7. Let $f_{1}$ be a row
labeled with L, and $f_{2}$ and $f_{3}$ two distinct LR-rows such that none of
them is nested in the others. Thus, we have three possibilities. If there are
three columns $j_{i}$, $i=1,2,3$, such that $f_{i}$ has a $1$ and the other
rows have a $0$, then we find $D_{7}$ as a subconfiguration of $A$. If instead
there are three rows $j_{i}$, $i=1,2,3$, such that $f_{i}$ and $f_{i+1}$ have
a $1$ and $f_{i+2}$ has a $0$ in $j_{i}$ (where subdindices are modulo 3),
then we find $D_{8}$ as a subconfiguration. The remaining possibility is that
there are 4 columns $j_{1},j_{2},j_{3},j_{4}$ such that $f_{1}$ and $f_{2}$
have a $1$ and $f_{3}$ has a $0$ in $j_{1}$, $f_{1}$ has a $1$ and $f_{2}$ and
$f_{3}$ have a $0$ in $j_{2}$, $f_{3}$ has a $1$ and $f_{1}$ and $f_{2}$ have
a $0$ in $j_{3}$, and $f_{2}$ and $f_{3}$ have a $1$ and $f_{1}$ has a $0$ in
$j_{4}$. Moreover, since all three rows are pairwise non-disjoint, either
there is a fifth column for which $f_{1}$ and $f_{3}$ have a $1$ and $f_{2}$
has a $0$ (in which case we find $D_{8}$ as a subconfiguration), or $f_{2}$
has a $1$ and $f_{1}$ and $f_{3}$ have a $0$ (in which case we have $D_{7}$ as
a subconfiguration), or all three rows have a $1$ in such column. In this
case, we find $D_{9}$ as a subconfiguration of $A$.

For assertion i of Definition 4.7, let $f_{1}$ and $f_{2}$ be two rows labeled
with L and R, respectively, and colored with distinct colors. Let $f_{3}$ and
$f_{4}$ be two LR-rows such that $f_{1}$ is neither disjoint nor contained in
$f_{3}$ and $f_{2}$ is neither disjoint nor contained in $f_{4}$. If $f_{1}$
is also not contained in $f_{4}$ or $f_{2}$ is not contained in $f_{3}$, then
we find $D_{9}$ as a subconfiguration. Thus, suppose that $f_{1}$ is contained
in $f_{4}$ and $f_{2}$ is contained in $f_{3}$. Moreover, we may assume that
for any column such that $f_{1}$ and $f_{3}$ have a $1$, $f_{2}$ has a $0$
(and analogously for $f_{2}$ and $f_{4}$ having a $1$ and $f_{1}$), for if not
we find $D_{5}$ as a subconfiguration. Hence, there is a column $j_{1}$ in $A$
having a $1$ in $f_{1}$ and $f_{4}$ and having a $0$ in $f_{3}$ and $f_{2}$,
and another column $j_{2}$ having a $1$ in $f_{2}$ and $f_{3}$ and having a
$0$ in $f_{1}$ and $f_{4}$. Moreover, since $f_{1}$ and $f_{3}$ are not
disjoint and $f_{2}$ and $f_{4}$ are not disjoint (and $f_{1}$ is nested in
$f_{4}$ and $f_{2}$ is nested in $f_{3}$), there are columns $j_{3}$ and
$j_{4}$ such that $f_{1}$, $f_{3}$ and $f_{4}$ have a $1$ and $f_{2}$ has a
$0$ in $j_{3}$ and $f_{2}$, $f_{3}$ and $f_{4}$ have a $1$ and $f_{1}$ has a
$0$. Therefore, we find $D_{10}$ as a subconfiguration of $A$.

It follows by using a similar argument as for the previous assertions that, if
$A$ does not satisfy assertion j, then that there is $D_{11}$, $D_{12}$ or
$D_{13}$ as a subconfiguration in $A$, and this finishes the proof. ∎

######  Corollary 4.9.

Every enriched matrix $A$ that admits a total block bi-coloring contains none
of the matrices in $\mathcal{D}$. Equivalently, if $A$ admits a total block
bi-coloring, then every property listed in 4.7 hold.

Another example of families of enriched matrices that do not admit a total
block bi-coloring are $\mathcal{S}$ and $\mathcal{P}$, which are the matrices
shown in Figures 10 and 11, respectively. Therefore, since the existence of a
total block bi-coloring is a property inherited by subconfigurations, if an
enriched matrix $A$ admits a total block bi-coloring, then $A$ contains none
of the matrices in $\mathcal{S}$ or $\mathcal{P}$. With this in mind, we give
the following definition which is also a characterization by forbidden
subconfigurations.

######  Definition 4.10.

Let $A$ be an enriched matrix. We say $A$ is _admissible_ if and only if $A$
is $\\{\mathcal{D},\mathcal{S},\mathcal{P}\\}$-free.

###  4.2 Partially 2-nested matrices

This section is organized as follows. First, we give some definitions that
will help us obtain a characterization of LR-orderable matrices (see
Definition 3.5) by forbidden subconfigurations. Afterwards, we define and
characterise partially $2$-nested matrices, which are those enriched matrices
that admit an LR-ordering and for which the given coloring of the labeled rows
of $A$ induces a partial block bi-coloring.

######  Definition 4.11.

A _tagged matrix_ is a matrix $A$, each of whose rows is either uncolored or
colored with blue or red, together with a set of at most two distinguished
columns of $A$. These distinguished columns will be refered to as _tag
columns_.

######  Definition 4.12.

Let $A$ be an enriched matrix. The _tagged matrix of $A$_, denoted by
$A_{\mathrm{tag}}$, is a tagged matrix whose underlying matrix is obtained
from $A$ by adding two columns, $c_{L}$ and $c_{R}$, such that:

  1. (1)

the column $c_{L}$ has a $1$ if $f$ is labeled L or LR and $0$ otherwise,

  2. (2)

the column $c_{R}$ has a $1$ if $f$ is labeled R or LR and $0$ otherwise, and

  3. (3)

the set of distinguished columns of $A_{\mathrm{tag}}$ is $\\{c_{L},c_{R}\\}$.

We denote $A^{*}_{\mathrm{tag}}$ to the tagged matrix of $A^{*}$ (recall
Definition 4.4). By simplicity we will consider column $c_{L}$ as the first
and column $c_{R}$ as the last column of $A_{\mathrm{tag}}$ and
$A^{*}_{\mathrm{tag}}$. We consider all the rows of $A_{\mathrm{tag}}$ and
$A^{*}_{\mathrm{tag}}$ colored with the same (or no) color as in $A$.

$\displaystyle A_{\mathrm{tag}}=\scriptsize{\bordermatrix{&c_{L}\hskip
19.91692ptc_{R}\cr&\boldsymbol{1}10001\boldsymbol{1}\cr&\boldsymbol{1}11001\boldsymbol{1}\cr&\boldsymbol{0}01100\boldsymbol{0}\cr&\boldsymbol{1}11100\boldsymbol{0}\cr&\boldsymbol{1}00000\boldsymbol{1}\cr&\boldsymbol{0}00111\boldsymbol{1}}\
\begin{matrix}\\\ \\\ \\\
{\color[rgb]{0.94140625,0.1953125,0.234375}\bullet}\\\
{\color[rgb]{0,0,1}\bullet}\\\ {\color[rgb]{0,0,1}\bullet}\end{matrix}}$
$\displaystyle A^{*}_{\mathrm{tag}}=\scriptsize{\bordermatrix{&c_{L}\hskip
19.91692ptc_{R}\cr&\boldsymbol{0}\boldsymbol{1}\boldsymbol{1}\boldsymbol{1}\boldsymbol{1}\boldsymbol{1}\boldsymbol{1}\cr&\boldsymbol{1}\boldsymbol{1}\boldsymbol{1}\boldsymbol{1}\boldsymbol{1}\boldsymbol{1}\boldsymbol{0}\cr&\boldsymbol{0}01110\boldsymbol{0}\cr&\boldsymbol{0}00110\boldsymbol{0}\cr&\boldsymbol{0}01100\boldsymbol{0}\cr&\boldsymbol{1}11100\boldsymbol{0}\cr&\boldsymbol{0}00111\boldsymbol{1}}\
\begin{matrix}\\\ \\\ \\\ \\\
{\color[rgb]{0.94140625,0.1953125,0.234375}\bullet}\\\
{\color[rgb]{0,0,1}\bullet}\\\ {\color[rgb]{0,0,1}\bullet}\end{matrix}}$
Figure 14: Example of $A_{\mathrm{tag}}$ and $A^{*}_{\mathrm{tag}}$ for the
matrix $A$ in Figure 6(a). The first two bold rows of $A^{*}_{\mathrm{tag}}$
are its distinguished rows, added by definition.

The following remarks allow us to simplify the proof of the characterization
of LR-orderable matrices.

######  Remark 2.

If $A^{*}_{\mathrm{tag}}$ has the C$1$P, then the distinguished rows force the
tag columns $c_{L}$ and $c_{R}$ to be the first and last columns of
$A^{*}_{\mathrm{tag}}$, respectively.

######  Remark 3.

An admissible matrix $A$ is LR-orderable if and only if the tagged matrix
$A^{*}_{\mathrm{tag}}$ has the C$1$P.

######  Lemma 4.13.

An admissible matrix $A$ is LR-orderable if and only if the tagged matrix
$A^{*}_{\mathrm{tag}}$ contains neither Tucker matrices nor the tagged
matrices of the family $\mathcal{M}$ depicted in Figure 12 as
subconfigurations.

###### Proof.

$\Rightarrow)$ This follows from the last remark and Theorem 4.5.

$\Leftarrow)$ Suppose that the tagged matrix $A^{*}_{\mathrm{tag}}$ does not
contain any of the above listed matrices as subconfigurations, and still the
C$1$P does not hold for the rows of $A^{*}_{\mathrm{tag}}$.

Hence, there is a Tucker matrix $M$ such that $M$ is a subconfiguration of
$A^{*}_{\mathrm{tag}}$. Notice that, if $M$ does not have any tag column of
$A^{*}_{\mathrm{tag}}$, then $M$ is a subconfiguration of $A$. Hence, $A$ does
not have the C$1$P and therefore the result follows. Henceforth, we assume
that at least one column of $M$ is a tag column of $A^{*}_{\mathrm{tag}}$.
Suppose without loss of generality that, if $M$ intersects only one tag
column, then this tag column is $c_{L}$, since the analysis is symmetric if
assumed otherwise and gives as a result in each case the dual matrix.

Case (1) Suppose first that $M$ intersects one or both of the distinguished
rows. Thus, $M$ is $M_{V}$, $M_{I}(3)$, or $M_{II}(k)$ for some $k\geq 3$. We
consider each case separately.

Case (1.1)  $M=M_{V}$. In this case, the distinguished row is $(1,1,1,1,0)$
and thus the last column of $M$ is a tag column. Hence we find
$M_{5}^{\prime}$ in $A^{*}_{\mathrm{tag}}$, which results in a contradiction.

Case (1.2)  $M=M_{I}(3)$. If $(1,1,0)$ is a distinguished row, then we find
$D_{0}$ as a subconfiguration given by the second and third rows. It is
symmetric if the distinguished row is either the second or the third row, and
therefore this case is not possible.

Case (1.3)  $M=M_{II}(k)$. In this case, the distinguished rows of
$A^{*}_{\mathrm{tag}}$ can correspond only to the first and the last row of
$M$. Suppose only the first row $(0,1,\ldots,1)$ of $M$ corresponds to a
distinguished row of $A^{*}_{\mathrm{tag}}$. Thus, the first column of $M$ is
precisely a tag column of $A^{*}_{\mathrm{tag}}$. Hence, $M_{2}^{\prime}(k)$
is a subconfiguration of $A_{\mathrm{tag}}$, and this results in a
contradiction. The same holds if instead the last row is the sole
distinguished row.

Finally, suppose both the first and the last row of $M$ correspond to the
distinguished rows of $A^{*}_{\mathrm{tag}}$. If this is the case, then the
columns $1$ and $k-1$ of $M$ correspond to the tag columns of
$A^{*}_{\mathrm{tag}}$. Suppose first that $M=M_{II}(4)$. In this case, every
row of $M$ is colored, since every row corresponds to a row of $A$ labeled
with either L or R. Moreover, the first and second row of $M$ are colored with
distinct colors, for if not we find $D_{1}$ as a subconfiguration of $A$. The
same holds for the second and third row of $M$, and also for the third and
fourth row of $M$. However, this implies that the second and third row of $M$
induce $D_{2}$ in $A$, hence this case is not possible.

If instead $M=M_{II}(k)$ for $k\geq 5$, then $M_{2}^{\prime\prime}(k)$ is a
subconfiguration of $A^{*}_{\mathrm{tag}}$, and thus we reach a contradiction.

Case (2) Suppose that $M$ does not intersect any distinguished rows of
$A^{*}_{\mathrm{tag}}$.

Suppose first that exactly one of the columns in $M$ is a tag column.

Case (2.1)  $M=M_{I}(k)$. Notice that, if any of the columns of $M$ is a tag
column of $A^{*}_{\mathrm{tag}}$, then we find $D_{0}$ as a subconfiguration
of $A$, which results in $A$ not being admissible and thus reaching a
contradiction.

Case (2.2)  $M=M_{II}(k)$. As in the previous case, some of the columns of $M$
cannot be tag columns of $A^{*}_{\mathrm{tag}}$. If there is only one tag
column, then he only remaining possibilities for tag columns in $M$ are column
$1$ or column $k-1$, for in any other case we find $D_{0}$ as a
subconfiguration of $A$. Analogously, if instead $M$ intersects both tag
columns of $A^{*}_{\mathrm{tag}}$, then such columns are also columns $1$ and
$k-1$. However, if $c_{L}$ is either column $1$ or column $k-1$, then
$M_{2}^{\prime\prime}(k)$ is a subconfiguration of $A^{*}_{\mathrm{tag}}$.
Analogously, if $c_{R}$ is either column $1$ or $k-1$ of $M$, then we find the
dual matrix of $M_{2}^{\prime}(k)$ as a subconfiguration.

Finally, suppose that two columns are tag columns. Notice that the first and
second rows of $M$ are colored with distinct colors, for if not we find
$D_{1}$ as a subconfiguration of $A$. The same holds for the last two rows of
$M$. Hence, if $k=4$, then we find $D_{2}$ as a subconfiguration od $A$ given
by the second and third rows. If instead $k>5$, then $M_{2}^{\prime\prime}(k)$
is a subconfiguration of $A^{*}_{\mathrm{tag}}$, which results once more in a
contradiction.

Case (2.3)  $M=M_{III}(k)$. In this case, the only possibilities for tag
columns in $M$ are column $1$, column $k-1$ and column $k$, for if not we find
$D_{0}$ as a subconfiguration of $A$.

Suppose first that the tag column of $A^{*}_{\mathrm{tag}}$ is the first
column of $M$. In that case, we find $M_{3}^{\prime}(k)$ as a subconfiguration
of $A^{*}_{\mathrm{tag}}$, which also results in a contradiction. If instead
the tag column is column $k$, then we use an analogous reasoning to find
$M_{3}^{\prime\prime}(k)$ as a subconfiguration of $A^{*}_{\mathrm{tag}}$ and
thus reaching a contradiction.

Suppose now that both the first column and the last column of $M$ are tag
columns. Since $A$ is admissible, this case is not possible for the first and
last row induce $D_{1}$ or $D_{2}$ as subconfigurations, depending on whether
the rows are colored with the same color or with distinct colors,
respectively.

Case (2.4)  $M=M_{IV}$. In this case, the columns of $M$ that could be tag
columns are column $1$, column $3$ and column $5$, for if any other column of
$M$ is a tag column of $A^{*}_{\mathrm{tag}}$, we find $D_{0}$ as a
subconfiguration of $A$, thus contradicting the hypothesis of admissibility of
$A$. Furthermore, the choice of the tag column is symmetric since there is a
reordering of the rows that allows us to obtain the same matrix if the tag
column is either column $1$, column $3$ or column $5$, regardless of the
choice of the column. Hence, there are two possibilities: when column $1$ is
the only tag column of $A^{*}_{\mathrm{tag}}$ in $M$, and when the two tag
columns of $A^{*}_{\mathrm{tag}}$ are columns $1$ and $3$ of $M$. If column
$1$ is the only tag column, then we find $M_{4}^{\prime}$ as a
subconfiguration of $A^{*}_{\mathrm{tag}}$. If instead the columns $1$ and $3$
are both tag columns, then the first and the second row of $M$ are colored
with the same color, for if not there is $S_{3}(3)$ as a subconfiguration of
$A$ and this is not possible since $A$ is admissible. Thus, in this case we
find $M_{4}^{\prime\prime}$ as a subconfiguration of $A^{*}_{\mathrm{tag}}$.

Case (2.5)  $M=M_{V}$. Once more and using the same argument, the only columns
that could be tag columns of $A^{*}_{\mathrm{tag}}$ are columns $2$, $3$ or
$5$. Moreover, if the second column of $M$ is the sole tag column, then there
is a reordering of the rows such that the matrix obtained is the same as the
matrix when the third column is the tag column. If column $5$ is the only tag
column, then we find $M_{5}^{\prime}$ as a subconfiguration as in Case 1.1. If
instead column $2$ is the only tag column, then the first and second rows of
$M$ have the same color, for if not we find $S_{2}(3)$ as a subconfiguration
of $A$, and thus we find $M_{5}^{\prime\prime}$ as a subconfiguration of
$A^{*}_{\mathrm{tag}}$. Finally, if columns $2$ and $5$ are both tag columns
of $A^{*}_{\mathrm{tag}}$, then the first and last row of $M$ induce $D_{2}$
as a subconfiguration, disregarding the coloring of the rows and thus this
case is also not possible.

Therefore, we reached a contradiction by assuming that the C$1$P does not hold
for $A^{*}_{\mathrm{tag}}$ if $A^{*}_{\mathrm{tag}}$ contains the listed
subconfigurations. ∎

Let $A$ be an enriched matrix and let $A_{LR}$ be the enriched submatrix of
$A$ consisting precisely of all the LR-rows of $A$. We give a useful property
for this enriched submatrix when $A$ is admissible.

######  Lemma 4.14.

If $A$ is admissible, then $A_{LR}$ contains no $F_{1}(k)$ or $F_{2}(k)$, for
every odd $k\geq 5$.

###### Proof.

Toward a contradiction, suppose that $A_{LR}$ contains $F_{1}(k)$ or
$F_{2}(k)$ as a subconfiguration, for some odd $k\geq 5$. Since $k\geq 5$, we
find the following subconfiguration in $A$:

$\displaystyle\scriptsize{\bordermatrix{&\cr\textbf{LR}&1100\cr\textbf{LR}&0110\cr\textbf{LR}&0011}\
}$

Since these three rows induce $D_{13}$, we reach a contradiction. It follows
analogously that there is no $F_{2}(k)$ in $A_{LR}$. Therefore, $A_{LR}$
contains neither $F_{1}(k)$ nor $F_{2}(k)$, for every odd $k\geq 5$. ∎

######  Remark 4.

It follows from Lemma 4.14 that, if $A$ is admissible, then there is a
partition of the LR-rows of $A$ into two subsets $S_{1}$ and $S_{2}$ such that
every pair of rows in each subset are either nested or disjoint. Moreover,
since $A$ contains no $D_{11}$ as a subconfiguration, every pair of LR-rows
that lie in the same subset $S_{i}$ are nested, for each $i=1,2$.
Equivalently, the LR-rows in each subset $S_{i}$ are totally ordered by
inclusion, for each $i=1,2$.

When giving the guidelines to draw a circle model for any split graph
$G=(K,S)$, not only is it important that the matrix $A(S_{i},K_{i})$ for each
partition $K_{i}$ of $K$ results admissible and LR-orderable. We also need to
ensure that there exists an LR-ordering in which every LR-row that is split
into an L-block and an R-block satisfies a couple more properties than the
ones given by the LR-ordering itself. The following definition states the
necessary conditions for the LR-ordering that we need to consider to obtain a
circle model. We call this a _suitable LR-ordering_. The lemma that follows
ensures that, if a matrix $A$ is admissible and LR-orderable, then we can
always find a suitable LR-ordering for the columns of $A$.

######  Definition 4.15.

An LR-ordering $\Pi$ is _suitable_ if the L-blocks of those LR-rows with
exactly two blocks are disjoint with every R-block, the R-blocks of those LR-
rows with exactly two blocks are disjoint with the L-blocks and, for each LR-
row, the intersection with any U-block is empty with either its L-block or its
R-block.

######  Lemma 4.16.

If $A$ is admissible, LR-orderable and contains no $M_{0}$, $M_{II}(4)$,
$M_{V}$ or $S_{0}(k)$ as a subconfiguration for every even $k\geq 4$, then it
has at least one suitable LR-ordering.

###### Proof.

Let $A$ be an admissible LR-orderable matrix. Toward a contradiction, suppose
that every LR-ordering is non-suitable. If $\Pi$ is an LR-ordering of $A$,
then either (1) there is a U-block $u$ and an LR-row $f_{1}$ such that $u$ is
not disjoint with the L-block and the R-block of $f_{1}$, or (2) there is an
LR-row $f_{1}$ such that its L-block is not disjoint with some R-block, since
$\Pi$ is non-suitable. In both cases, there is no possible reordering of the
columns to obtain a suitable LR-ordering.

Since $A$ is admissible, it follows from Lemma 4 that the LR-rows can be split
into a two set partition such that the LR-rows in each set are totally
ordered. Moreover, any two LR-rows for which the L-block of one intersects the
R-block of the other are in distinct sets of the partition and thus the
columns may be reordered by moving the portion of the block that one of the
rows has in common with the other all the way to the right (or left). Hence,
if two such blocks intersect and there is no possible LR-reordering of the
columns, then there is at least one non-LR-row blocking the reordering.
Throughout the proof and for simplicity, we will say that a row or block _$a$
is chained to the left (resp. to the right) of another row or block $b$_ if
$a$ and $b$ overlap and $a$ intersects $b$ in column $l(b)$ (resp. $r(b)$).

Case (1) Let $a_{1}$ be the L-block of $f_{1}$ and $b_{1}$ be the R-block of
$f_{1}$. Suppose first there is a U-block $u$ such that $u$ intersects both
$a_{1}$ and $b_{1}$.

Let $j_{1}=r(a_{1})+1$, this is, the first column in which $f_{1}$ has a $0$,
$j_{2}=r(a_{1})$ and $j_{3}=l(b_{1})$ in which both rows $f_{1}$ and $u$ have
a $1$. Since it is not possible to rearrange the columns to obtain a suitable
LR-ordering, in particular, there are two columns $j_{4}<j_{2}$ and
$j_{5}>j_{3}$ in which $u$ has $0$, one before and one after the string of
$1$’s of $u$. Moreover, there is at least one row $f_{2}$ distinct to $f_{1}$
and $u$ blocking the reordering of the columns $j_{1}$, $j_{2}$ and $j_{3}$.

Case (1.1)  Suppose $f_{2}$ is the only row blocking the reordering. Notice
that $f_{2}$ is neither disjoint nor nested with $u$ and there is at least one
column in which $f_{1}$ has a $0$ and $f_{2}$ has a $1$. We may assume without
loss of generality that this is column $j_{1}$. Suppose $f_{2}$ is unlabeled.
The only possibility is that $f_{2}$ overlaps with $u$, $a_{1}$ and $b_{1}$,
for if not we can reorder the columns to obtain a suitable LR-ordering. In
that case, we find $M_{0}$ as a subconfiguration in $A$. If instead $f_{2}$ is
labeled with either L or R, then we find $S_{6}^{\prime}(3)$ as a
subconfiguration in $A$ considering columns $j_{4}$, $j_{2}$, $j_{1}$,
$j_{3}$, $j_{5}$ and both tag columns. If $f_{2}$ is an LR-row and $f_{2}$ is
the only row blocking the reordering, then either the L-block of $f_{2}$ is
nested in the L-block of $f_{1}$ and the R-block of $f_{2}$ contains the
R-block of $f_{1}$, or vice versa. However, in that case we can move the
portion of the L-block of $f_{1}$ that intersects $u$ to the right and thus we
find a suitable LR-ordering, therefore this case is not possible.

Case (1.2)  Suppose now there is a sequence of rows $f_{2},\ldots,f_{k}$ for
some $k\geq 3$ blocking the reordering such that $f_{i}$ and $f_{i+1}$ overlap
for each $i\in\\{2,\ldots,k\\}$. Moreover, there is either –at least– one row
that overlaps $a_{1}$ or $b_{1}$. We may assume without loss of generality
that $f_{2}$ is such a row and that $f_{2}$ and $b_{1}$ overlap. Suppose that
$f_{2}$ and $f_{3}$ are unlabeled rows. Notice that, either all the rows are
chained to the left of $f_{2}$ or to the right. Furthermore, since $A$
contains no $M_{0}$ as a subconfiguration and we assumed that $b_{1}$ and
$f_{2}$ overlap, if $f_{i}$ is chained to the left of $f_{2}$, then $f_{i}$ is
contained in $b_{1}$ for every $i\geq 3$, and if $f_{i}$ is chained to the
right of $f_{2}$, then $f_{i}$ is contained in $u$ for every $3\leq i<k$. In
either case, we find $M_{II}(4)$ as a subconfiguration considering the columns
$j_{2}$, $j_{1}$, $j_{3}$ and $j_{5}$. Suppose that $f_{2}$ is the only
labeled row in the sequence and that $f_{2}$ is labeled with R. If $u$ and
$f_{2}$ overlap, then we find $S_{6}^{\prime}(3)$ as a subconfiguration as in
the previous paragraphs. Thus, we assume $u$ is nested in $f_{2}$. Since the
sequence of rows is blocking the reordering, the rows $f_{3},\ldots,f_{k}$ are
chained one to one to the right and $f_{k}=u$, therefore we find $S_{6}(k)$ as
a subconfiguration. The only remaining possibility is that there are two
labeled rows in the sequence blocking the reordering. Since $A$ contains
neither $D_{1}$ nor $S_{3}(3)$ as a subconfiguration, then either these two
rows are labeled with the same letter and nested, or they are labeled one with
L and the other with R and are disjoint. We may assume without loss of
generality that $f_{2}$ and $f_{k}$ are such labeled rows.

If $f_{2}$ and $f_{k}$ are both labeled with L, then necessarily one is nested
in the other, for $\Pi$ is an LR-ordering. In that case, one has a $0$ in
column $j_{1}$ and the other has a $1$ there, for if not we can reorder the
columns moving $j_{1}$ –and maybe some other columns in which $f_{1}$ has a
$0$– to the right. Hence, in this case we find $S_{5}(k)$ as a
subconfiguration induced by rows $f_{1},f_{2},\ldots,f_{k}$It is analogous if
$f_{2}$ and $f_{k}$ are labeled with R.

If instead $f_{2}$ and $f_{k}$ are labeled one with L and the other with R,
then there are two possibilities. Either $f_{2},\ldots,f_{k-1}$ are nested in
$a_{1}$, or $f_{2}$ is chained to the right of $u$ and $f_{3}$ is chained to
the left. In either case, if $f_{2}$ or $f_{3}$ have a $1$ in some column in
which $f_{1}$ has a $0$ and $u$ has a $1$, then we find $S_{6}^{\prime}(3)$ as
a subconfiguration. If instead $f_{3}$ is nested in $a_{1}$ and $f_{2}$ is
nested in $b_{1}$, then we find $M_{V}$ as a subconfiguration considering the
columns $j_{4}$, $j_{2}$, $j_{1}$, $j_{3}$ and $j_{5}$.

Case (2) Suppose now that there is a row $f_{2}$ such that the L-block $a_{1}$
of $f_{1}$ and the R-block $b_{2}$ of $f_{2}$ are not disjoint. Notice that,
by definition of R-block, $f_{2}$ is labeled with either R or LR. Once more,
we consider $j_{1}=r(a_{1})+1$, the first column in which $f_{1}$ has a $0$.

Since $a_{1}$ and $b_{2}$ intersect, there is a column $j_{2}<j_{1}$ such that
$a_{1}$ and $b_{2}$ both have a $1$ in column $j_{2}$.

Case (2.1)  Suppose first that there is exactly one row $f_{3}$ blocking the
possibility of reordering the columns to obtain a suitable LR-ordering. Notice
that, for a row to block the reordering of the columns, such row must have a
$1$ in $j_{2}$ and at least one column with a $0$. We have three possible
cases:

Case (2.1.1)  Suppose first that $f_{3}$ is unlabeled. If $f_{2}$ is labeled
with LR and $f_{3}$ does not intersect the L-block of $f_{2}$, then we can
move to the R-block of $f_{1}$ those columns in which $f_{3}$ has $0$ and
$a_{1}$ has $1$. If $f_{3}$ intersects the L-block of $f_{2}$, then this is
precisely as in the previous case. Thus, we assume $f_{2}$ is labeled with R.
If $f_{3}$ is not nested in either $f_{1}$ nor $f_{2}$, then there is a column
$j_{3}$ in which $f_{3}$ and $f_{2}$ have a $1$ and $f_{1}$ has a $0$, and a
column $j_{4}$ in which $f_{3}$ and $f_{1}$ have a $1$ and $f_{2}$ has a $0$.
In that case, we find $S_{6}(3)$ as a subconfiguration considering the columns
$j_{1}$, $j_{2}$, $j_{3}$, $j_{4}$ and both tag columns. If $f_{3}$ is nested
in $f_{2}$, then we can rearrange the columns by moving to the right all the
columns in which $a_{1}$ and $f_{2}$ both have $1$ and mantaining those
columns in which $f_{3}$ has a $1$ together. If instead $f_{3}$ is nested in
$f_{1}$, then we find $S_{6}^{\prime}(3)$ as a subconfiguration.

Case (2.1.2)  Suppose now that $f_{3}$ is labeled with L. If $f_{2}$ is
labeled with R, then $f_{2}$ and $f_{3}$ are colored with distinct colors, for
if not we find $D_{1}$ as a subconfiguration. Thus, we find $D_{5}$ as a
subconfiguration induced by $f_{1}$, $f_{2}$, $f_{3}$. Moreover, notice that,
if $f_{3}$ is also labeled with R, then it is possible to move all those
columns of $a_{1}$ that have a $1$ and intersect $f_{2}$ (and $f_{3}$) in
order to obtain a suitable LR-ordering and thus $f_{3}$ did not block the
reordering. If instead $f_{2}$ is an LR-row, then we find either $D_{7}$,
$D_{8}$ or $D_{9}$ as a subconfiguration, depending on where is the string of
$0$’s in row $f_{3}$. Also notice that it is indistinct in this case if
$f_{3}$ is labeled with R.

Case (2.1.3)  Suppose $f_{3}$ is labeled with LR. Since $A$ is admissible, if
$f_{2}$ is an LR-row, then either $f_{3}$ is nested in $f_{1}$ or $f_{3}$ is
nested in $f_{2}$ (we may assume this since it is analogous if $f_{3}$
contains $f_{1}$ or $f_{2}$: we will see that $f_{3}$ is not blocking the
reordering). If $f_{3}$ is nested in $f_{2}$, then we can move the part of the
L-block $a_{1}$ that intersects $b_{2}$ all the way to the right and then we
have a suitable reordering. It is analogous if $f_{3}$ is nested in $f_{1}$.
If $f_{2}$ is labeled with R, then we may assume that $f_{2}$ is not nested in
$f_{3}$, for if not we have a similar situation as in the previous paragraphs.
The same holds if $f_{1}$ and $f_{3}$ are nested LR-rows. We know that the
L-block $a_{3}$ of $f_{3}$ intersects the R-block $b_{2}$ Hence, in the column
$j_{3}=r(a_{3})+1$ the row $f_{3}$ has a $0$ and $f_{2}$ has a $1$, and in the
column $j_{4}=l(b_{2})-1$ the row $f_{3}$ has a $1$ and $f_{2}$ has a $0$.
Moreover, since $f_{1}$ and $f_{3}$ are not nested, then there is a column
greater than $j_{2}$ in which $f_{1}$ has a $0$ and $f_{2}$ and $f_{3}$ have a
$1$. In this case, we find $D_{8}$ as a subconfiguration.

Case (2.2)  Suppose now that it is not possible to reorder the columns to
obtain a suitable LR-ordering, since there is a sequence of rows
$f_{3},\ldots,f_{k}$, with $k>3$, blocking –in particular– the reordering of
the columns $j_{1}=r(a_{1})+1$ and $j_{2}=r(a_{1})$.

We may assume that the sequence of rows is either chained to the right –and
thus $f_{k}$ is labeled with R– or to the left –and thus $f_{k}$ is labeled
with L, for if not we find $M_{V}$ as a subconfiguration as in the first case.
Suppose that $f_{2}$ is labeled with R. If the sequence $f_{3},\ldots,f_{k}$
is chained to the left, then we find $S_{4}(k)$ as a subconfiguration. If
instead the sequence $f_{3},\ldots,f_{k}$ is chained to the right, then we
find $S_{1}(k)$ as a subconfiguration. Suppose now that $f_{2}$ is an LR-row.
Since the L-block of $f_{1}$ and the R-block of $f_{2}$ intersect, then these
rows are not nested. Whether the sequence is chained to the right or to the
left, we may assume that $f_{3}$ is nested in $a_{1}$ and is disjoint with
$a_{2}$. Let $k$ be the number of $0$’s between the L-block and the R-block of
$f_{2}$. Depending on whether $k$ is odd or even, we find $S_{0}(k)$ or
$S_{8}(k)$, respectively, as a subconfiguration of the subconfiguration given
by considering the rows $f_{1},f_{2},\ldots,f_{k+3}$. This finishes the proof.

∎

######  Definition 4.17.

Let $A$ be an enriched matrix. We say $A$ is _partially $2$-nested_ if all the
following assertions hold:

  1. 1.

$A$ is admissible, LR-orderable and contains no $M_{0}$, $M_{II}(4)$, $M_{V}$
or $S_{0}(k)$ as a subconfiguration for any even $k\geq 4$.

  2. 2.

Each pair of non-LR-rows colored with the same color are either disjoint or
nested in $A$.

  3. 3.

If an L-block (resp. R-block) of an LR-row is colored, then any non-LR-row
colored with the same color is either disjoint or contained in such L-block
(resp. R-block).

  4. 4.

If an L-block (resp. R-block) of an LR-row $f_{1}$ is colored and there is a
distinct LR-row $f_{2}$ for which its L-block (resp. R-block) is also colored
with the same color, then $f_{1}$ and $f_{2}$ are nested in $A$.

######  Remark 5.

The second assertion of the definition of partially $2$-nested implies that
there are no monochromatic gems or monochromatic weak gems in $A$ because $A$
is admissible and thus any two labeled non-LR-rows induce no $D_{1}$ as a
subconfiguration. Moreover, the third assertion implies that there are no
monochromatic weak gems in $A$. Furthermore, the last statement implies that
there are no badly-colored doubly-weak gems in $A$.

The following Corollary is a straightforward consequence of Remark 5 and Lemma
4.13.

######  Corollary 4.18.

An admissible matrix $A$ is partially $2$-nested if and only if $A$ contains
as a subconfiguration no $M_{0}$, $M_{II}(4)$, $M_{V}$, monochromatic gems nor
monochromatic weak gems nor badly-colored doubly-weak gems and the tagged
matrix $A^{*}_{\mathrm{tag}}$ does not contain any Tucker matrices,
$M_{2}^{\prime}(k)$, $M_{2}^{\prime\prime}(k)$, $M_{3}^{\prime}(k)$,
$M_{3}^{\prime\prime}(k)$ for $k\geq 3$, $M_{4}^{\prime}$,
$M_{4}^{\prime\prime}$, $M_{5}^{\prime}$, $M_{5}^{\prime\prime}$ as a
subconfiguration.

###  4.3 A characterization of $2$-nested matrices

We begin this section by stating and proving a lemma that characterises when a
partial $2$-coloring can be extended to a total proper $2$-coloring, for every
partially $2$-colored connected graph $G$. Then, we give the definition and
some properties of the auxiliary matrix $A+$. These properties will be helpful
throughout the proof of Theorem 4.6 at the end of the section.

######  Lemma 4.19.

Let $G$ be a connected graph with a partial proper $2$-coloring of the
vertices. Then, the partial $2$-coloring can be extended to a total proper
$2$-coloring of the vertices of $G$ if and only if all of the following
conditions hold:

  * •

There are no even induced paths such that the only colored vertices of the
path are its endpoints, and they are colored with distinct colors.

  * •

There are no odd induced paths such that the only colored vertices of the path
are its endpoints, and they are colored with the same color.

  * •

There are no induced uncolored odd cycles.

  * •

There are no induced odd cycles with exactly one colored vertex.

  * •

There are no induced odd cycles with exactly two consecutive colored vertices.

###### Proof.

The ‘only if’ part is trivial.

On the other hand, for the ‘if’ part, suppose all of the conditions hold.
Notice that, since $G$ has a given proper partial $2$-coloring, then there are
no adjacent vertices pre-colored with the same color. We denote $(G,f)$ to
refer to $G$ and the given partial proper $2$-coloring $f$ of its vertices.

Let $H$ be the subgraph of $G$ induced by its uncolored vertices and let $f$
be the given proper partial $2$-coloring of $V(G)$. The proof is by induction
on the number of vertices of $H$.

For the base case, this is to say when $|H|=1$, let $v$ be in $H$. If $v$
cannot be colored, then there are two distinct vertices $x_{1}$ and $x_{2}$
such that $x_{1}$ and $x_{2}$ have different colors. Thus, the set
$\\{x_{1},v,x_{2}\\}$ either induces an even path in $G$ of length 2 with the
endpoints colored with distinct colors, or an induced $C_{3}$ with exactly one
uncolored vertex, which results in a contradiction.

For the inductive step, suppose that we can extend the partial $2$-coloring of
$G$ to a proper $2$-coloring if $|V(H)|\leq k$. Suppose that $|V(H)|=k+1$. If
$H$ is not connected, then the result follows by applying the induction
hypothesis to each of its connected components. Moreover, if $H$ is
disconnected from $G\left[G-H\right]$, then $H$ is an uncolored graph with no
odd cycles, thus we can extend $f$ using any proper $2$-coloring for $H$.
Henceforth, we assume $H$ is connected and there is a vertex in $H$ having at
least one neighbour in $V(G-H)$.

Let $v$ in $H$ be any vertex such that $N(v)\cap V(G-H)\neq\emptyset$. Every
vertex $w$ in $N(v)\cap V(G-H)$ must be colored with the same color, for if
not we find either an induced cycle of length $3$ with exactly one uncolored
vertex or an even induced path with its endpoints colored with distinct
colors. Suppose that such a color is red. Thus, we extend the given partial
proper $2$-coloring $f$ to $f^{\prime}$ assigning the color blue to $v$. We
will see that the graph $G$ with the partial proper $2$-coloring $f^{\prime}$
fulfills all the assertions.

It is straightforward that there are no uncolored odd cycles in
$(G,f^{\prime})$, for there were no odd uncolored cycles in $(G,f^{\prime})$.
Furthermore, using the same argument, we see that there are no induced odd
cycles with exactly one colored vertex nor induced odd cycles with exactly two
consecutive colored vertices, for this would imply that there is either an odd
uncolored cycle or an odd cycle with exactly one colored vertex in $(G,f)$.

Since all the assertions hold for $(G,f)$, if there was an even induced path
$P=<v_{1},\ldots,v_{j}>$ such that the only colored vertices are its endpoints
and they are colored with distinct colors, then the only possibility is that
one of such endpoints is $v$. Let $v=v_{1}$. Notice that $v_{2}$ lies in
$H\setminus\\{v\\}$, thus it is uncolored in both $(G,f)$ and
$(G,f^{\prime})$. Let $w\in N(v)\cap V(G-H)$. Notice that $wv_{j}\not\in
E(G)$, for they are both colored with red. If $w$ is nonadjacent to every
vertex in $P$ with the exception of $v=v_{1}$, then $<P,w>$ is an odd induced
path in $(G,f)$ such that the only colored vertices are its endpoints and are
both colored with the same color. Suppose to the contrary that $w$ is adjacent
to at least one vertex in $P$. If $w$ is adjacent to a vertex in $P$ with an
even index, then let us consider $v_{i}$ to be the neighbour of $w$ in $P$
with the smaller even index. In this case, we find an induced odd cycle
$<w,v=v_{1},\ldots,v_{i},w>$ with exactly one colored vertex in
$(G,f^{\prime})$, and this is equivalent to having an induced odd cycle with
exactly one colored vertex in $(G,f)$, which results in a contradiction. If
instead $w$ is adjacent to a vertex in $P$ having an odd index, then we
consider $v_{i}$ to be the neighbour of $w$ in $P$ with the largest odd index.
In this case, we find $<w,v_{i},\ldots,v_{j}>$ which is an induced path of
length $j-i+1$ –which is odd– in $(G,f)$ such that the only colored vertices
are $w$ and $v_{j}$ and they are colored with the same color, and this
contradicts one of the assertions.

The same argument holds if there is an odd induced path in $(G,f^{\prime})$. ∎

Let $A$ be an admissible matrix, let $S_{1}$ and $S_{2}$ be a partition of the
LR-rows of $A$ such that every pair of rows in $S_{i}$ is nested, for each
$i=1,2$. Since $A$ contains no $D_{0}$ as a subconfiguration, there is a row
$m_{L}$ such that $m_{L}$ is labeled with L and contains every L-block of
those rows in $A$ that are labeled with L. Analogously, we find a row $m_{R}$
such that every R-block of a row in $A$ labeled with R is contained in
$m_{R}$. Moreover, there are two rows $m_{1}$ in $S_{1}$ and $m_{2}$ in
$S_{2}$ such that every row in $S_{i}$ is contained in $m_{i}$, for each
$i=1,2$. This property allows us to define the following auxiliary matrix,
which will be helpful throughout the proof of Theorem 4.6.

######  Definition 4.20.

Let $A$ be an admissible matrix and let $\Pi$ be a suitable LR-ordering of
$A$. The enriched matrix $A+$ is the result of applying the following rules to
$A$:

  * •

Every empty row is deleted.

  * •

Each LR-row $f$ with exactly one block is replaced by a row labeled with
either L or R, depending on whether it has an L-block or an R-block.

  * •

Each LR-row $f$ with exactly two blocks, is replaced by two uncolored rows,
one having a $1$ in precisely the columns of its L-block and labeled with L,
and another having a $1$ in precisely the columns of its R-block and labeled
with R. We add a column $c_{f}$ with $1$ in precisely these two rows and $0$
in the remaining ones.

  * •

If there is at least one row labeled with L or R in $A$, then each LR-row $f$
whose entries are all $1$’s is replaced by two uncolored rows, one having a
$1$ in precisely the columns of the maximum L-block and labeled with L, and
another having a $1$ in precisely the complement of the maximum L-block and
labeled with R. We add a column $c_{f}$ with $1$ in precisely these two rows
and $0$ in the remaining ones.

Notice that every non-LR-row remains the same. See Figure 15 for an example.

$\displaystyle B=\scriptsize{\bordermatrix{\leavevmode\nobreak\
&\leavevmode\nobreak\
\cr\textbf{LR}&10000\cr\textbf{LR}&11001\cr\textbf{LR}&11111\cr&01100\cr\textbf{L}&11100\cr\textbf{LR}&00000\cr\textbf{R}&00011}\,\begin{matrix}\\\
\\\ \\\ \\\ {\color[rgb]{0.94140625,0.1953125,0.234375}\bullet}\\\
{\color[rgb]{0,0,1}\bullet}\\\ {\color[rgb]{0,0,1}\bullet}\end{matrix}}$
$\displaystyle
B+=\scriptsize{\bordermatrix{&\cr\textbf{L}&1000000\cr\textbf{L}&1100010\cr\textbf{R}&0000110\cr\textbf{L}&1110001\cr\textbf{R}&0001101\cr&0110000\cr\textbf{L}&1110000\cr\textbf{R}&0001100}\,\begin{matrix}\\\
\\\ \\\ \\\ \\\ \\\ {\color[rgb]{0.94140625,0.1953125,0.234375}\bullet}\\\
{\color[rgb]{0,0,1}\bullet}\\\ \end{matrix}}$ Figure 15: Example of an
enriched admissible matrix $B$ and $B+$. The last two columns of $B+$ are
$c_{r_{2}}$ and $c_{r_{3}}$.

######  Remark 6.

Let $A$ be a partially $2$-nested matrix. Since $A$ is admissible, LR-
orderable and contains no $M_{0}$, $M_{II}(4)$, $M_{V}$ or $S_{0}(k)$ for
every even $k\geq 4$ as a subconfiguration, then by Lemma 4.16 we know that
there exists a suitable LR-ordering $\Pi$. Hence, whenever we define the
auxiliary matrix $A+$ for such a matrix $A$, we will always consider a
suitable LR-ordering $\Pi$ to do so.

Let us consider $A+$ as defined in Definition 4.20 according to a suitable LR-
ordering $\Pi$. Suppose there is at least one LR-row in $A$. Recall that,
since $A$ is admissible, the LR-rows may be split into two disjoint subsets
$S_{1}$ and $S_{2}$ such that the LR-rows in each subset are totally ordered
by inclusion. This implies that there is an inclusion-wise maximal LR-row
$m_{i}$ for each $S_{i}$, $i=1,2$. If we assume that $m_{1}$ and $m_{2}$
overlap, then either the L-block of $m_{1}$ is contained in the L-block of
$m_{2}$ and the R-block of $m_{1}$ contains the R-block of $m_{2}$, or vice
versa. Since $\Pi$ is suitable and $A$ contains neither $D_{1}$ nor $D_{4}$ as
a subconfiguration and has no uncolored rows labeled with either L or R, if
there is at least one LR-row in $A$, then the following holds:

  * •

There is an inclusion-wise maximal L-block $b_{L}$ in $A+$ such that every
R-block in $A+$ is disjoint with $b_{L}$.

  * •

There is an inclusion-wise maximal R-block $b_{R}$ in $A+$ such that every
L-block in $A+$ is disjoint with $b_{L}$.

Therefore, when defining $A+$ we replace each LR-row having two blocks by two
distinct rows, one labeled with L and the other labeled with R, such that the
new row labeled with L does not intersect with any row labeled with R and the
new row labeled with R does not intersect with any row labeled with L.

Notice that $A$ differs from $A+$ only in its LR-rows, which are either
deleted or replaced in $A+$ by labeled uncolored rows.

######  Definition 4.21.

A color assignment to some (eventually none) of the blocks of an enriched
matrix $A$ using two colors is a _proper $2$-coloring_ if $A$ is admissible,
the L-block and R-block of each LR-row of $A$ are colored with distinct
colors, and $A$ contains no monochromatic gems, weak monochromatic gems or
badly-colored doubly-weak gems as subconfigurations. If there is no (resp. at
least one) uncolored row in $A$, then we say that the proper $2$-coloring is
_total_ (resp.  _partial_).

Given an assignment of two colors to some (eventually none) of the blocks an
enriched matrix $A$ using two colors, we say it is a _proper $2$-coloring of
$A+$_ if it is a proper $2$-coloring of $A$.

######  Remark 7.

Let $A$ be an enriched matrix. If $A$ is admissible, then the given coloring
of the blocks is a proper $2$-coloring. This follows from the fact that every
colored row is either labeled with L or R, or is an empty LR-row, thus there
are no monochromatic gems, monochromatic weak gems or badly-colored weak gems
in $A$ for they would induce $D_{1}$.

The following is a straightforward consequence of Remark 5.

######  Lemma 4.22.

Let $A$ be an enriched matrix. If $A$ is partially $2$-nested, then the given
coloring of $A$ is a proper partial $2$-coloring. Moreover, if $A$ is
partially $2$-nested and admits a total $2$-coloring, then $A$ with such
$2$-coloring is partially $2$-nested.

######  Lemma 4.23.

Let $A$ be an enriched matrix. Then, $A$ is $2$-nested if $A$ is partially
$2$-nested and the given partial block bi-coloring of $A$ can be extended to a
total proper $2$-coloring of $A$.

###### Proof.

Let $A$ be an enriched matrix that is partially $2$-nested and for which the
given coloring of the blocks can be extended to a total proper $2$-coloring of
$A$. In particular, this induces a total block bi-coloring for $A$. Indeed, we
want to see that a proper $2$-coloring induces a total block bi-coloring for
$A$. Notice that the only pre-colored rows may be those labeled with L or R
and those empty LR-rows. Let us see that each of the assertions of Definition
3.7 hold.

  1. 1.

Since $A$ is an enriched matrix and the only rows that are not pre-colored are
the nonempty LR-rows and those that correspond to U-blocks, then there is no
ambiguity when considering the coloring of the blocks of a pre-colored row
(Assertion 2 of Definition 3.7).

  2. 2.

If $A$ is partially $2$-nested, then in particular is admissible, LR-orderable
and contains no $M_{0}$, $M_{II}(4)$ or $M_{V}$ as a subconfiguration. Thus,
by Lemma 4.16, there is a suitable LR-ordering $\Pi$ for the columns of $A$.
We consider $A$ ordered according to $\Pi$ from now on. Since $\Pi$ is
suitable, then every L-block of an LR-row and an R-block of a non-LR-row are
disjoint, and the same holds for every R-block of an LR-row and an L-block of
a non-LR-row (assertion 4 of Definition 3.7).

  3. 3.

Since $A$ is admissible, it contains as a subconfigurations no matrix in
$\mathcal{D}$. Moreover, since $A$ is partially $2$-nested, by Corollary 4.18
there are no monochromatic gems or weak gems and no badly-colored doubly-weak
gems induced by pre-colored rows. It follows from this and the fact that the
LR-ordering is suitable, that assertion 8 of Definition 3.7 holds.

  4. 4.

The pre-coloring of the blocks of $A$ can be extended to a total proper
$2$-coloring of $A$. This induces a total block bi-coloring for $A$, for which
we can deduce the following assertions:

     * •

Since there is a total proper $2$-coloring of $A$, in particular the L-block
and R-block of each LR-row are colored with distinct colors. (Assertion 1 of
Definition 3.7).

     * •

Each L-block and R-block corresponding to distinct LR-rows with nonempty
intersection are also colored with distinct colors since there are no badly-
colored doubly-weak gems in $A$ (Assertion 9 of Definition 3.7).

     * •

Since $A$ is admissible, every L-block and R-block corresponding to distinct
non-LR-rows are colored with different colors since there is no $D_{1}$ in $A$
(Assertion 5 of Definition 3.7).

     * •

Since there are no monochromatic weak gems in $A$, an L-block of an LR-row and
an L-block of a non-LR-row that contains the L-block must be colored with
distinct colors. Furthermore, if any L-block and a U-block are not disjoint
and are colored with the same color, then the U-block is contained in the
L-block. (Assertions 3 and 7 of Definition 3.7).

     * •

There is no monochromatic gem in $A$, then each two U-blocks colored with the
same color are either disjoint or nested. (Assertion 6 of Definition 3.7).

∎

######  Lemma 4.24.

Let $A$ be an enriched matrix. If $A$ admits a suitable LR-ordering, then $A$
contains no $M_{0}$, $M_{II}(4)$, $M_{V}$ or $S_{0}(k)$ as a subconfiguration
for any even $k\geq 4$.

###### Proof.

The result follows trivially if $A$ contains no LR-rows because $A$ admits an
LR-ordering. Thus, if we consider $A$ without its LR-rows, that submatrix has
the C$1$P and hence it contains no Tucker matrix as a subconfiguration. Toward
a contradiction, suppose that $A$ contains either $M_{0}$, $M_{II}(4)$,
$M_{V}$ or $S_{0}(k)$ as a subconfiguration for some even $k\geq 4$. Since it
contains no $M_{I}(k)$ as a subconfiguration for every $k\geq 3$, in
particular there is no $M_{0}$ or $S_{0}(k)$ where at most one of the rows is
an LR-row. Moreover, it is easy to see that, if we reorder the columns of
$M_{0}$, then there is no possible LR-ordering in which every L-block and
every R-block are disjoint. Similarly, consider $S_{0}(4)$, whose first row
has a $1$ in every column. We may assume that the last row is an LR-row for
any other reordering of the columns yields an analogous situation with one of
the rows. However, whether the first row is unlabeled or not, the first and
the last row prevent a suitable LR-ordering. The reasoning is analogous for
any even $k>4$.

Suppose that $A$ contains $M_{V}$ as a subconfiguration, and let
$f_{1}$,$f_{2}$, $f_{3}$ and $f_{4}$ be the rows of $M_{V}$ depicted as
follows:

$M_{V}=\scriptsize{\bordermatrix{&\cr f_{1}&11000\cr f_{2}&00110\cr
f_{3}&11110\cr f_{4}&10011}}$

If the first row is an LR-row, then either $f_{3}$ or $f_{4}$ is an LR-row,
for if not we find $M_{I}(3)$ in $A^{*}$ as a subconfiguration, which is not
possible because there is an LR-ordering in $A$. The same holds if the second
row is an LR-row. If $f_{3}$ is an LR-row, then $f_{4}$ is an LR-row, for if
not $f_{4}$ must have only one block. Thus, if $f_{4}$ is an unlabeled row,
then it intersects both blocks of $f_{3}$, and if $f_{4}$ is an R-row, then
its R-block intersects the L-block of $f_{3}$. However, if we move the columns
so that the L-block of $f_{3}$ does not intersect the R-block of $f_{4}$, then
we either cannot split $f_{1}$ into two blocks such that one starts on the
left and the other ends on the right, or we cannot maintain a single block in
$f_{2}$. It follows analogously if we assume that $f_{4}$ is an LR-row, thus
$f_{1}$ is not an LR-row. By symmetry, we assume that $f_{2}$ is also a non-
LR-row, and thus the proof is analogous if only $f_{3}$ and $f_{4}$ may be LR-
rows.

Suppose $A$ contains $M_{II}(4)$ as a subconfiguration. Let us denote $f_{1}$,
$f_{2}$, $f_{3}$ and $f_{4}$ to the rows of $M_{II}(4)$ depicted as follows:

$M_{II}(4)=\scriptsize{\bordermatrix{&\cr f_{1}&0111\cr f_{2}&1100\cr
f_{3}&0110\cr f_{4}&1101}}$

If $f_{2}$ is an LR-row, then necessarily $f_{3}$ or $f_{4}$ are LR-rows, for
if not we find $M_{I}(3)$ in $A^{*}$. If only $f_{2}$ and $f_{3}$ are LR-rows,
then we find $M_{II}(4)$ as a subconfiguration in $A^{*}$. If instead only
$f_{2}$ and $f_{4}$ are LR-rows, then –as it is– whether $f_{1}$ is an R-row
or an unlabeled row, the block of $f_{1}$ intersects the L-block and the
R-block of $f_{4}$ (and also the L-block of $f_{2}$). The only possibility is
to move the second column all the way to the right and split $f_{2}$ into two
blocks and give the R-block of $f_{4}$ length $2$. However in this case, it is
not possible to move another column and obtain an ordering that keeps all the
$1$’s consecutive for $f_{3}$ and $f_{1}$ not intersecting both blocks of
$f_{4}$ simultaneously. Thus, $f_{1}$ is also an LR-row. However, for any
ordering of the columns, either it is not possible to simultaneously split the
string of $1$’s in $f_{1}$ and keep the L-block of $f_{2}$ starting on the
left, or it is not possible to simultaneously maintain the string of $1$’s in
$f_{3}$ consecutive and the L-block of $f_{1}$ disjoint with the R-block of
$f_{4}$. It follows analogously if both $f_{3}$ and $f_{4}$ are LR-rows.
Hence, $f_{2}$ is a non-LR-row, and by symmetry, we may assume that $f_{3}$ is
also a non-LR-row. Suppose now that $f_{1}$ is an LR-row. If $f_{4}$ is not an
LR-row, then there is no possible way to reorder the columns and having a
consecutive string of $1$’s for the rows $f_{2}$, $f_{3}$ and $f_{4}$
simultaneously, unless we move the fourth column all the way to the left.
However in that case, either $f_{4}$ is an L-row and its L-block intersects
the R-block of $f_{1}$ of it is an unlabeled row that intersects both blocks
of $f_{1}$. Moreover, the same holds if $f_{4}$ is an LR-row, with the
difference that in this case the R-block of $f_{4}$ intersects the L-block of
$f_{1}$ or the string of $1$’s in $f_{2}$ and $f_{3}$ is not consecutive.∎

######  Lemma 4.25.

Let $A$ be an enriched matrix with a block bi-coloring. If $A$ is $2$-nested,
then $A$ is partially $2$-nested and the total block bi-coloring induces a
proper total $2$-coloring of $A$.

###### Proof.

If $A$ is $2$-nested, then in particular there is an LR-ordering $\Pi$ for the
columns. Moreover, by assertions 4 and 7 of Definition 3.7, such an ordering
is suitable.

Suppose first there is a monochromatic gem in $A$. Such a gem is not induced
by two unlabeled rows since in that case assertion 6 of Definition 3.7 would
not hold. Hence, such a gem is induced by at least one labeled row. Moreover,
if one is a labeled row and the other is an unlabeled row, then assertion 7 of
Definition 3.7 would not hold. Thus, both rows are labeled. By assertion 5 of
Definition 3.7, if the gem is induced by two non-disjoint L-block and R-block,
then it is not monochromatic, disregarding on whether they correspond to LR-
rows or non-LR-rows. Hence, exactly one of the rows is an LR-row. However, by
assertion 4 of Definition 3.7, an L-block of an LR-row and an R-block of a
non-LR-row are disjoint, thus they cannot induce a gem.

Suppose there is a monochromatic weak gem in $A$, thus at least one of its
rows is a labeled row. It is not possible that exactly one of its rows is a
labeled row and the other is an unlabeled row, since assertion 7 of Definition
3.7 holds. Moreover, these rows do not correspond to rows labeled with L and
R, respectively, for assertions 4 and 5 of Definition 3.7 hold. Furthermore,
both rows of the weak gem are LR-rows, since if exactly one is an LR-row, then
assertions 3, 4 and 7 of Definition 3.7 hold and thus it is not possible to
have a weak gem. However, in that case, assertion 5 of Definition 3.7
guarantees that this is also not possible.

Finally, there is no badly-colored doubly-weak gem since assertions 4, 5 and 9
of Definition 3.7 hold.

Now, let us see that $A$ is admissible. Since there is an LR-ordering of the
columns, there are no $D_{0}$, $D_{2}$, $D_{3}$, $D_{6}$, $D_{7}$, $D_{8}$ or
$D_{11}$ contained as a subconfiguration in $A$. Moreover, by assertion 5 of
Definition 3.7, there is no $D_{1}$ contained in $A$ as a subconfiguration. As
we have previously seen, there are no monochromatic gems or monochromatic weak
gems. Hence, it is easy to see that if there is a total block bi-coloring,
then $A$ contains none of the matrices in $\mathcal{S}$ or $\mathcal{P}$ as a
subconfiguration. Suppose $A$ contains $D_{4}$ as a subconfiguration. By
assertion 8 of Definition 3.7, if there are two L-blocks of non-LR-rows
colored with distinct colors, then every LR-row has a nonempty L-block, and in
this case such an L-block is contained in both rows labeled with L. However,
by assertion 3 of Definition 3.7, the L-block of the LR-row is properly
contained in the L-blocks of the non-LR-rows, thus it must be colored with a
distinct color than the color assigned to each L-block of a non-LR-row, and
this leads to a contradiction. By assertion 3 of Definition 3.7, there is no
$D_{5}$ contained in $A$ as a subconfiguration. Let us suppose $A$ contains
$D_{9}$ as a subconfiguration induced by the rows $f_{1}$, $f_{2}$ and
$f_{3}$, where $f_{1}$ is labeled with L and $f_{2}$ and $f_{3}$ are LR-rows.
Suppose that $f_{1}$ is colored with red. Since the L-block of $f_{2}$ is
contained in $f_{1}$, by assertion 3 of Definition 3.7, then the L-block of
$f_{2}$ is colored with blue. The same holds for the L-block of $f_{3}$.
However, $f_{2}$ and $f_{3}$ are not nested, thus by by assertion 9 of
Definition 3.7, the L-blocks of $f_{2}$ and $f_{3}$ are colored with distinct
colors, which results in a contradiction.

Let us suppose $A$ contains $D_{10}$ as a subconfiguration induced by the rows
$f_{1}$, $f_{2}$, $f_{3}$ and $f_{4}$, where $f_{1}$ is labeled with L and
colored with red, $f_{2}$ is labeled with R and colored with blue, and $f_{3}$
and $f_{4}$ are LR-rows. Since the L-block of $f_{3}$ is properly contained in
$f_{1}$, then by assertion 3 of Definition 3.7, it is colored with blue. By
assertion 1 of Definition 3.7, the R-block of $f_{3}$ is colored with red.
Using a similar argument, we assert that the R-block of $f_{4}$ is colored
with red and the L-block of $f_{4}$ is colored with blue. However, $f_{3}$ and
$f_{4}$ are non-disjoint and non-nested, thus the L-block of $f_{3}$ and the
R-block of $f_{4}$ are colored with distinct colors, which results in a
contradiction.

By Lemma 4.24, since there is a suitable LR-ordering, then $A$ contains no
$M_{0}$, $M_{II}(4)$, $M_{V}$ or $S_{0}(k)$ as a subconfiguration for any even
$k\geq 4$.

It follows from assertion 9 of Definition 3.7 and the fact that there is an
LR-ordering, that $A$ contains neither $D_{12}$ nor $D_{13}$ as a
subconfiguration. Therefore $A$ is partially $2$-nested.

Finally, we will see that the total block bi-coloring for $A$ induces a proper
total $2$-coloring of $A$. Since all the assertions of Definition 3.7 hold, it
is straightforward that there are no monochromatic gems or monochromatic weak
gems or badly-colored weak gems in $A$. For more details on this, see Remark 5
and Lemma 4.23 since the same arguments are detailed there. Moreover, since
assertion 1 of Definition 3.7 holds, the L-block and R-block of the same LR-
row are colored with distinct colors. Therefore, it follows that a total block
bi-coloring of $A$ induces a proper total $2$-coloring of $A$. ∎

The following corollary is a straightforward consequence of the previous
results.

######  Corollary 4.26.

Let $A$ be an enriched matrix. If $A$ is partially $2$-nested and $B$ is
obtained from $A$ by extending its partial coloring to a total proper
$2$-coloring, then $B$ is $2$-nested if and only if for each LR-row its
L-block and R-block are colored with distinct colors and $B$ contains no
monochromatic gems, monochromatic weak gems or badly-colored doubly-weak gems
as subconfigurations.

The main result of this work is Theorem 4.6, whose proof follows directly from
Theorem 4.27 –which was proven in [15]– and Theorem 4.28, whose proof will be
given below.

######  Theorem 4.27 ([15]).

Let $A$ be an enriched matrix such that every row of $A$ is unlabeled. Then,
$A$ is $2$-nested if and only if $A$ contains no $F_{0}$, $F_{1}(k)$,
$F_{2}(k)$ or their dual matrices for every odd $k\geq 5$ as subconfigurations
(see Figure 9)

Theorem 4.27 is a particular case of Theorem 4.6. More precisely, this theorem
gives necessary and suficient conditions for an enriched matrix with all
unlabeled –and thus uncolored– rows to be $2$-nested. Notice that such an
enriched matrix is simply a $(0,1)$-matrix. Moreover, the condition of being
$2$-nested for this particular case reduces to admiting a C$1$P ordering and a
$2$-coloring assignment for the rows such that both the red and blue
subconfigurations are nested matrices.

For the remaining enriched matrices –this is, for every enriched matrix with
at least one labeled row– we have the following lemma that characterises all
the forbidden subconfigurations.

######  Theorem 4.28.

Let $A$ be an enriched matrix such that $A$ has at least one labeled row.
Then, $A$ is $2$-nested if and only if $A$ contains none of the following
listed matrices or their dual matrices as subconfigurations:

  * •

$M_{0}$, $M_{II}(4)$, $M_{V}$ or $S_{0}(k)$ for every even $k$ (See Figure 7)

  * •

Every enriched matrix in the family $\mathcal{D}$ (See Figure 8)

  * •

Every enriched matrix in the family $\mathcal{F}$ (See Figure 9)

  * •

Every enriched matrix in the family $\mathcal{S}$ (See Figure 10)

  * •

Every enriched matrix in the family $\mathcal{P}$ (See Figure 11)

  * •

Monochromatic gems, monochromatic weak gems, badly-colored doubly-weak gems

and $A^{*}$ contains no Tucker matrices and none of the enriched matrices in
$\mathcal{M}$ or their dual matrices as subconfigurations (See Figure 12).

The proof is organized as follows. The ‘only if’ part follows almost
immediately using Lemma 4.25 and the characterizations of admissibility, LR-
orderable and partially $2$-nested given throughout this section. For the ‘if’
part, we will define an auxiliary graph $H(A)$ that is partially $2$-colored
according to the pre-coloring of the blocks of $A$. Toward a contradiction, we
suppose that $H(A)$ is not bipartite. Using the characterization given in
Lemma 4.19, we know there is one of the $5$ possible kinds of paths or cycles.
We analyse each case and reach a contradiction.

###### Proof.

Let $A$ be an enriched matrix with at least one labeled row in $A$ (labeled
with L, R or LR), and suppose $A$ is $2$-nested. In particular, $A$ is
partially $2$-nested with the given coloring and the block bi-coloring induces
a total proper $2$-coloring of $A$. Thus, by Corollary 4.18, $A$ is admissible
and contains no $M_{0}$, $M_{II}(4)$, $M_{V}$, $S_{0}(k)$ for any even $k\geq
4$, monochromatic gems, monochromatic weak gems or badly-colored doubly-weak
gems as subconfigurations, and $A^{*}_{\mathrm{tag}}$ contains no Tucker
matrices, $M_{4}^{\prime}$, $M_{4}^{\prime\prime}$, $M_{5}^{\prime}$,
$M_{5}^{\prime\prime}$, $M^{\prime}_{2}(k)$, $M^{\prime\prime}_{2}(k)$,
$M_{3}^{\prime}(k)$, $M_{3}^{\prime\prime}(k)$,
$M_{3}^{\prime\prime\prime}(k)$, for any $k\geq 4$ as subconfigurations. In
particular, since $A$ is admissible, there is no $D_{13}$ induced by any three
LR-rows.

Moreover, notice that every pair of consecutive rows of any of the matrices
$F_{0}$, $F_{1}(k)$, and $F_{2}(k)$ for all odd $k\geq 5$ induces a gem, and
there is an odd number of rows in each matrix. Thus, if one of these matrices
is a submatrix of $A_{\mathrm{tag}}$, then there is no proper $2$-coloring of
the blocks. Therefore, $A$ contains no $F_{0}$, $F_{1}(k)$, and $F_{2}(k)$ for
any odd $k\geq 5$ as subconfigurations. A similar argument holds for
$F^{\prime}_{0}$, $F_{1}^{\prime}(k)$, $F_{2}^{\prime}(k)$, changing ’gem’ by
’weak gem’ whenever one of the two rows considered is a labeled row.

Conversely, suppose $A$ is not $2$-nested. Henceforth, we assume that $A$ is
admissible.

If $A$ is not partially $2$-nested, then either $A$ contains $M_{0}$,
$M_{II}(4)$, $M_{V}$, $S_{0}(k)$ for some even $k\geq 4$ as a
subconfiguration, or there is a subconfiguration of $M$ in
$A^{*}_{\mathrm{tag}}$ such that $M$ is one of the forbidden subconfigurations
for partially $2$-nested stated above. Henceforth, we assume that $A$ is
partially $2$-nested.

If $A$ is partially $2$-nested but is not $2$-nested, then the pre-coloring of
the rows of $A$ (which is a proper partial $2$-coloring of $A$ since $A$ is
admissible) cannot be extended to a total proper $2$-coloring of $A$.

We wish to extend the partial pre-coloring given for $A$. By Corollary 4.26,
if $B$ is obtained by extending the pre-coloring of $A$ and $B$ is $2$-nested,
then neither two blocks corresponding to the same LR-row are colored with the
same color, nor there are monochromatic gems, monochromatic weak gems or
badly-colored doubly-weak gems in $B$. Let us consider the auxiliary matrix
$A+$, defined from a suitable LR-ordering $\Pi$ of the columns of $A$. Notice
that, if there is at least one labeled row in $A$, then there is at least one
labeled row in $A+$ and these labeled rows in $A+$ correspond to rows of $A$
that are labeled with either L, R, or LR.

We now define a graph $H=H(A+)$, whose vertices are the rows of $A+$. We say a
vertex is an _LR-vertex (resp. non-LR vertex)_ if it corresponds to a block of
an LR-row (resp. non-LR-row) of $A$. The adjacencies in $H$ are as follows:

  * •

Two non-LR vertices are adjacent in $H$ if the underlying uncolored submatrix
of $A$ determined by these two rows contains a gem or a weak gem as a
subconfiguration.

  * •

Two LR-vertices corresponding to the same LR-row in $A$ are adjacent in $H$.

  * •

Two LR-vertices $v_{1}$ and $v_{2}$ corresponding to distinct LR-rows are
adjacent if $v_{1}$ and $v_{2}$ are labeled with the same letter in $A+$ and
the LR-rows corresponding to $v_{1}$ and $v_{2}$ overlap in $A$.

  * •

An LR-vertex $v_{1}$ and a non-LR vertex $v_{2}$ are adjacent in $H$ if the
rows corresponding to $v_{1}$ and $v_{2}$ are not disjoint and $v_{2}$ is not
contained in $v_{1}$.

The vertices of $H$ are partially colored with the pre-coloring given for the
rows of $A$.

Notice that every pair of vertices corresponding to the same LR-row $f$
induces a gem in $A+$ that contains the column $c_{f}$, and two adjacent LR-
vertices $v_{1}$ and $v_{2}$ in $H$ do not induce any kind of gem in $A+$,
except when considering both columns $c_{r_{1}}$ and $c_{r_{2}}$.

Let us consider a path $P$ in the graph $H$. We say a subpath $Q$ of $P$ is an
_LR-subpath_ if every vertex in $Q$ is an LR-vertex. We say an LR-subpath $Q$
in $P$ is _maximal_ if $Q$ is not properly contained in any other LR-subpath
of $P$. We say that two LR-vertices $v_{i}$ and $v_{j}$ are _consecutive_ in
the path $P$ (resp. in a cycle $C$ in $H$) if either $j=i+1$ or $v_{l}$ is
unlabeled for every $l=i+1,\ldots,j-1$.

The following claims will be useful throughout the proof.

###### Claim 1

Let $C$ be a cycle in $H=H(A+)$. Then, there are at most 3 consecutive LR-
vertices labeled with the same letter. The same holds for any path $P$ in $H$.

Let $v_{1}$, $v_{2}$ and $v_{3}$ be 3 consecutive LR-vertices in $H$, all
labeled with the same letter. Notice that any subset in $H$ of LR-vertices
labeled with the same letter in $A+$ corresponds to a subset of the same size
of distinct LR-rows in $A$. By definition, two LR-vertices are adjacent in $H$
only if they are labeled with the same letter and the corresponding rows in
$A$ contain a gem, or equivalently, if they are not nested. Moreover, notice
that once the columns of $A$ are ordered according to $\Pi$, these rows have a
$1$ in the first non-tag column and a $1$ in the last non-tag column. Hence,
if there are 4 consecutive LR-vertices $v_{1}$, $v_{2}$, $v_{3}$ and $v_{4}$
in the cycle $C$ of $H$ and all of them are labeled with the same letter, then
$v_{1}$ and $v_{2}$ are not nested, $v_{2}$ and $v_{3}$ are not nested and
$v_{1}$ and $v_{3}$ must be nested. Thus, since $v_{2}$ and $v_{4}$ and
$v_{1}$ and $v_{4}$ are also nested, then $v_{4}$ either contains $v_{1}$ and
$v_{2}$, or is nested in both. In either case, since $v_{3}$ and $v_{4}$ are
not nested, then $v_{1}$ and $v_{3}$ are not nested and this results in a
contradiction. $\diamondsuit$

###### Claim 2

There are at most 6 uncolored labeled consecutive vertices in $C$. The same
holds for any path $P$ in $H$.

This follows from the previous claim and the fact that every pair of uncolored
labeled vertices labeled with distinct rows are adjacent only if they
correspond to the same LR-row in $A$. $\diamondsuit$

If $A$ is not $2$-nested, then the partial $2$-coloring given for $H$ cannot
be extended to a total proper $2$-coloring of the vertices. Notice that the
only pre-colored vertices are those labeled with either L or R, and those LR
vertices corresponding to an empty row, which we are no longer considering
when defining $A+$. According to Lemma 4.19 we have 5 possible cases.

Case (1) There is an odd induced path $P=v_{1},v_{2},\ldots,v_{k}$ such that
the only colored vertices are $v_{1}$ and $v_{k}$, and they are colored with
the same color.

We assume without loss of generality throughout the proof that $v_{1}$ is
labeled with L, since it is analogous otherwise by symmetry. Recall that an
odd path is induced by an even number of vertices.

If $v_{2},\ldots,v_{k-1}$ are unlabeled rows, then we find either $S_{2}(k)$
or $S_{3}(k)$ as a subconfiguration which is not possible since $A$ is
admissible. Suppose there is at least one LR-vertex in $P$. Recall that, an
LR-vertex and a non-LR-vertex are adjcent in $H$ only if the rows in $A+$ are
both labeled with the same letter and the LR-row is properly contained in the
non-LR-row.

Suppose that every LR-vertex in $P$ is nonadjacent with each other. Let
$v_{i}$ be the first LR-vertex in $P$, and suppose first that $i=2$. Since
$v_{2}$ is an LR-vertex and is adjacent to $v_{1}$, then $v_{2}$ is labeled
with L and $v_{2}\subsetneq v_{1}$. Hence, since we are assuming there are no
adjacent LR-vertices in $P$ and $k\geq 4$, then $v_{3}$ is not an LR-vertex,
thus it is unlabeled because we are considering a suitable LR-ordering to
define $A+$. Let $v_{3},\ldots,v_{j}$ be the maximal sequence of consecutive
unlabeled vertices in $P$ that starts in $v_{3}$. Thus, $v_{l}\subseteq v_{1}$
for every $3\leq l\leq j$.

Notice that there are no other LR-vertices in $P$: toward a contradiction, let
$v_{j}$ be the next LR-vertex in $P$. If $v_{j}$ is labeled with L, then
$v_{j}$ is adjacent to $v_{1}$ since $v_{3}$ is nested in $v_{1}$, which is
not possible. It is analogous if $v_{j}$ is labeled with R. Thus, $v_{l}$ is
unlabeled for every $3\leq l\leq k-1$. Moreover, the vertex $v_{k}$ is labeled
with L, for if not we find $D_{1}$ in $A$ induced by $v_{1}$ and $v_{k}$ and
this is not possible since $A$ is admissible. However, in that case we find
$S_{5}(k)$ as a subconfiguration.

Hence, if $v_{i}$ is an isolated LR-vertex (this is, nonadjacent to other LR-
vertices), then $i>2$. It follows that $v_{2}$ is an unlabeled vertex. Notice
that a similar argument as in the previous paragraph proves that there are no
more LR-vertices in $P$: since $v_{i+1}$ is nested in $v_{i-1}$, it follows
that any other LR-vertex is adjacent to $v_{i-1}$. Suppose first that $v_{i}$
is labeled with L and let $v_{2},\ldots,v_{i-1}$ be the maximal sequence of
unlabeled vertices in $P$ that starts in $v_{2}$.

Since $v_{i}$ is the only LR-vertex in $P$, if $v_{k}$ is labeled with L, then
necessarily $i=k-1$ for if not $v_{k}$ is adjacent to $v_{i-1}$. However,
since in that case $v_{k}\supsetneq v_{k-1}=v_{i}$ and $v_{k}$ is nonadjacent
to every other vertex in $P$, then we find $S_{5}(k)$ as a subconfiguration.
Analogously, if $v_{k}$ is labeled with R, since $v_{j}\subseteq v_{i-1}$ for
every $j>i$, then $v_{k}$ is adjacent to $v_{i-1}$ which leads to a
contradiction.

Suppose now that $v_{i}$ is labeled with R and remember that $i>2$.