[#1][#1]

#  $\chi$-binding functions for squares of bipartite graphs and its subclasses

Dibyayan Chakraborty111School of Computing, University of Leeds, United
Kingdom L. Sunil Chandran222Indian Institute of Science, Bengaluru, India Dalu
Jacob22footnotemark: 2 Raji R. Pillai22footnotemark: 2

###### Abstract

A class of graphs $\mathcal{G}$ is $\chi$-bounded if there exists a function
$f$ such that $\chi(G)\leq f(\omega(G))$ for each graph $G\in\mathcal{G}$,
where $\chi(G)$ and $\omega(G)$ are the chromatic and clique number of $G$,
respectively. The _square_ of a graph $G$, denoted as $G^{2}$, is the graph
with the same vertex set as $G$ in which two vertices are adjacent when they
are at a distance at most two in $G$. In this paper, we study the
$\chi$-boundedness of _squares_ of bipartite graphs and its subclasses. Note
that the class of squares of graphs, in general, admit a quadratic
$\chi$-binding function. Moreover there exist bipartite graphs $B$ for which
$\chi\left(B^{2}\right)$ is
$\Omega\left(\frac{\left(\omega\left(B^{2}\right)\right)^{2}}{\log\omega\left(B^{2}\right)}\right)$.
We first ask the following question: “What sub-classes of bipartite graphs
have a linear $\chi$-binding function?” We focus on the class of _convex
bipartite_ graphs and prove the following result: for any convex bipartite
graph $G$, $\chi\left(G^{2}\right)\leq\frac{3\omega\left(G^{2}\right)}{2}$.
Our proof also yields a polynomial-time $3/2$-approximation algorithm for
coloring squares of convex bipartite graphs. We then introduce a notion called
“partite testable properties” for the squares of bipartite graphs. We say that
a _graph property $P$ is partite testable for the squares of bipartite graphs
if for a bipartite graph $G=(A,B,E)$, whenever the induced subgraphs
$G^{2}[A]$ and $G^{2}[B]$ satisfies the property $P$ then $G^{2}$ also
satisfies the property $P$_. Here, we discuss whether some of the well-known
graph properties like _perfectness_ , _chordality_ , _(anti-hole)-freeness_ ,
etc. are partite testable or not. As a consequence, we prove that the squares
of biconvex bipartite graphs are perfect.

Keywords: Bipartite graphs, Convex bipartite graphs, $\chi$-binding function,
Squares of graphs, Partite testable property.

##  1 Introduction

All the graphs we consider in the paper are finite, undirected, and simple.
For a graph $G$, we denote the vertex set as $V(G)$ and the edge set as
$E(G)$. A $k$-coloring of a graph $G$ is a mapping $c\colon
V(G)\rightarrow\\{1,2,\ldots,k\\}$ such that for any edge $uv\in E(G)$,
$c(u)\neq c(v)$. The _chromatic number_ of $G$, denoted by
$\chi\left(G\right)$, is the minimum integer $k$ such that $G$ admits a
$k$-coloring. The _clique number_ of a graph $G$, denoted by
$\omega\left(G\right)$, is the largest integer $k$ such that $G$ contains a
complete subgraph on $k$ vertices. A class of graphs $\mathcal{G}$ is
$\chi$-bounded if there exists a function $f$ such that $\chi(G)\leq
f(\omega(G))$ for each graph $G\in\mathcal{G}$, where $\chi(G)$ and
$\omega(G)$ are the chromatic and clique number of $G$, respectively. The
study on $\chi$-boundedness of graph classes has recently gained popularity
among researchers in the field. See the survey by Scott and Seymour [23].

In this paper, we study the $\chi$-boundedness of _squares_ of bipartite
graphs. The _square_ of a graph $G$, denoted as $G^{2}$, is the graph with the
same vertex set as $G$ in which two vertices are adjacent when they are at a
distance at most two in $G$. A graph $H$ is a _square_ graph if there exists a
graph $G$ such that $G^{2}\cong H$. Note that coloring square graphs is also
known as _distance $2$-coloring_ of graphs [20] and has applications in
broadcast scheduling in multi-hop radio networks, distributed computing, etc.
[11, 13].

Bounding the chromatic number of graph squares has been receiving attention
over the past 25 years. See a recent survey by Cranston [8].

Coloring squares of graphs is interesting, even for special classes of graphs.
Wegner’s conjecture on the chromatic number of squares of planar graphs is a
perfect example of this. In 1977, Wegner conjectured the following: Let $G$ be
a planar graph with maximum degree $\Delta$. If $\Delta=3$, then
$\chi(G^{2})\leq 7$, if $4\leq\Delta\leq 7$, then $\chi(G^{2})\leq\Delta+5$,
and if $\Delta\geq 8$, then
$\chi(G^{2})\leq\big{\lfloor}\frac{3\Delta}{2}\big{\rfloor}+1$. Wegner’s
conjecture for $\Delta=3$ has been confirmed by Thomassen [24]. But the
conjecture is still open for $\Delta\geq 4$. Due to the popularity of Wegner’s
conjecture, several upper bounds in terms of maximum degree are known for the
chromatic number of squares of planar graphs [1, 22, 27, 28]: in particular
for planar graphs with high girth [6, 9, 10]. Apart from planar graphs, there
are several other special classes of graphs, including cocomparability graphs,
circular-arc graphs, etc., for which the bounds on the chromatic number of
their squares are investigated [5].

Observe that if the maximum degree of a graph $G$ is $\Delta$, then the
maximum degree of $G^{2}$ is at most $\Delta^{2}$, and therefore we have
$\chi\left(G^{2}\right)\leq\Delta^{2}+1$. On the other hand, we can observe
that for any vertex $v\in V(G)$, the vertex $v$, together with its
neighborhood in $G$, form a clique in $G^{2}$. This implies that
$\omega(G^{2})\geq\Delta+1$. Together with the previous observation, we then
have $\chi(G^{2})\leq(\omega(G^{2})-1)^{2}+1$. Hence, the class of square
graphs is $\chi$-bounded with a quadratic $\chi$-binding function. Alon and
Mohar [2] have studied the upper and lower bounds for the chromatic number of
squares of graphs in terms of maximum degree. Since bipartite graphs are the
class of graphs having the least chromatic number, it would be interesting to
look at the chromatic number of the squares of bipartite graphs. In the
following section, we summarize our results and their significance.

###  1.1 Our results

First, we observe some implications of the result of Alon and Mohar [2]. In
particular, we show the existence of bipartite graphs $B$ such that the
chromatic number of $B^{2}$ is $\Omega(\frac{\omega^{2}}{\log\omega})$, where
$\omega$ is the clique number of $B^{2}$ (Observation 4). Furthermore, we also
observe that if the girth of a graph $G$ is greater than six, then the
chromatic number of $G^{2}$ is $O(\frac{\omega^{2}}{\log\omega})$, where
$\omega$ is the clique number of $G^{2}$ (Observation 1).

The above observation implies that the squares of bipartite graphs with girth
greater than six have a sub-quadratic $\chi$-binding function. But the
question of _whether the squares of (bipartite) graphs, in general, have a
sub-quadratic $\chi$-binding function or not_, remains open. In this paper, we
are interested in finding sub-classes of bipartite graphs, say $\mathcal{C}$
for which $\mathcal{C}^{2}$ (i.e. the class of graphs obtained by taking
squares of graphs in $\mathcal{C}$) has a linear $\chi$-binding function.
Specifically, we investigate the following question.

######  Question 1.

Identify some popular sub-classes of bipartite graphs whose squares admit a
linear $\chi$-binding function.

Let $G=(A,B,E)$ be a bipartite graph. Observe that while taking the square of
$G$, the set of edges whose endpoints are in different partite sets remain
unchanged in $G^{2}$, and the additional edges in $G^{2}$ appear only between
the vertices belonging to the same partite set. Also, note that
$\chi(G^{2})\leq\chi(G^{2}[A])+\chi(G^{2}[B])$. Therefore, the structure of
the graphs induced by the partite sets, $G^{2}[A]$ and $G^{2}[B]$, can have an
influence on the chromatic number of $G^{2}$. A graph $H$ is _perfect_ if for
every induced subgraph $H^{\prime}$ of $H$ we have
$\chi\left(H^{\prime}\right)=\omega\left(H^{\prime}\right)$. Since we are
particularly interested in finding the sub-classes of bipartite graphs that
admit a linear $\chi$-binding function, the bipartite graphs $G$ for which
$G^{2}[A]$ and $G^{2}[B]$ are _perfect_ is a natural candidate. Let
$\mathcal{C}$ be the class of bipartite graphs $G=(A,B,E)$ such that _both
$G^{2}[A]$ and $G^{2}[B]$ are perfect_. Then observe that for every graph $H$
in $\mathcal{C}^{2}$, we have $\chi\left(H\right)\leq 2\omega\left(H\right)$.
Interestingly, the class of _convex bipartite_ graphs is one such class of
bipartite graphs.

######  Definition 1 (Convex bipartite graph).

A bipartite graph $G=(A,B,E)$ is said to be convex bipartite if the vertices
in $B$ have an ordering such that, for each vertex $a\in A$, the vertices in
the neighborhood of $a$ in $G$ appear consecutively with respect to the
ordering.

Let $\mathcal{C}$ denote the class of convex bipartite graphs and $G=(A,B,E)$
be a graph in $\mathcal{C}$. Note that both $G^{2}[A]$ and $G^{2}[B]$ are
_interval graphs_ (a subclass of perfect graphs) in $G^{2}$ [21]. But, the
graphs in $\mathcal{C}^{2}$ need not be perfect. For example, the graph $G$
given in Figure 1 is a convex bipartite graph for which $G^{2}$ contains a
$C_{5}$, namely, $(v_{1},v_{2},v_{3},v_{4},v_{5})$ as an induced subgraph
(edges of $C_{5}$ are shown in red), and therefore, $G^{2}$ is not perfect.
Therefore, it would be interesting to see whether the trivial upper bound of
$2\omega(G^{2})$ for $\chi(G^{2})$ can be improved for $G\in\mathcal{C}$. Note
that in the literature, we can see similar instances of refining the trivial
$\chi$-binding function $2\omega$ to $3\omega/2$ for other special graph
classes as well. The _class of circular-arc graphs_ (intersection graphs of a
set of arcs on a circle) is such an example [25, 14, 26].

The following is one of the main results of this paper.

######  Theorem 1.

Let $G$ be a convex bipartite graph, and let $\omega(G^{2})$ denote the size
of a maximum clique in $G^{2}$. Then
$\chi(G^{2})\leq\big{\lfloor}\frac{3\omega(G^{2})}{2}\big{\rfloor}$. Moreover,
there exists a convex bipartite graph $H$, such that
$\chi(H^{2})\geq\frac{5\omega(H^{2})}{4}-2$.

Note that the squares of convex bipartite graphs may contain $K_{1,t}$ (for
arbitrarily large $t$), or arbitrarily large induced _cliques, paths, cycles
or wheels_ with odd or even parities, structures like _pyramid, diamond, gem,
$2K_{2}$, paraglider, chair_ etc. as induced subgraphs. Therefore, existing
results (e.g., [15, 16, 19, 3, 23]) that guarantee a $3\omega/2$
$\chi$-binding function for graphs that do not contain some of the above
structures as induced subgraphs, cannot be applied directly to prove Theorem
1. In 1879, while attempting to prove the Four Colour Theorem, Kempe [17]
introduced an elementary operation on graph coloring that later became known
as a _Kempe change_. Let $c$ be a $k$-coloring of a graph $G$. Then, a _Kempe
chain_ is a maximal bichromatic component. A _Kempe change_ in $c$ is
equivalent to swapping the two colors in a Kempe chain to produce a different
$k$-coloring of $G$.

We use this well-known Kempe change technique as a tool for proving Theorem 1.
Further, for a graph class, $\mathcal{C}$, as noted by Scott and Seymour [23],
the following question is also interesting.

######  Question 2.

For a graph class $\mathcal{C}$, is there a polynomial-time algorithm for
coloring graphs $G\in\mathcal{C}$ that uses only $f(\omega(G))$ colors, where
$f$ is the $\chi$-binding function for $\mathcal{C}$?

Recall that we prove in Theorem 1 that the class of squares of convex
bipartite graphs is $3\omega/2$-colorable. In fact, our proof also yields a
$3/2$-approximation algorithm for coloring the squares of convex bipartite
graphs and thereby answers the above question for the same class. Further, we
note that for a convex bipartite graph $G$, the function relating
$\chi(G^{2})$ and $\omega(G^{2})$ is not the same as the function relating
$\chi(G^{2})$ and $\Delta(G)$. In particular, if $G$ is a convex bipartite
graph with maximum degree $\Delta$, we prove that $\chi(G^{2})\leq 2\Delta$.
Moreover, there exist convex bipartite graphs with $\chi(G^{2})=2\Delta$
(Theorem 4).

The study on the structure of squares of convex bipartite graphs motivated us
to introduce the notion of _partite testable properties_ for the squares of
bipartite graphs, which is defined as follows.

######  Definition 2 (Partite testable property).

Let $\mathcal{C}$ be a class of bipartite graphs and let $P$ be a graph
property. We say that $P$ is a partite testable property for
$\mathcal{C}^{2}$, if for any bipartite graph $G=(A,B,E)$ in $\mathcal{C}$
whenever the induced subgraphs $G^{2}[A]$ and $G^{2}[B]$ satisfies the
property $P$ then $G^{2}$ also satisfies the property $P$.

For instance, in Theorem 5, we prove that _the property of not containing odd
anti-holes of length greater than five is a partite testable property for the
squares of bipartite graphs in general_. i.e. for a bipartite graph
$G=(A,B,E)$ if $G^{2}[A]$ and $G^{2}[B]$ do not contain odd anti-holes of
length greater than five, then $G^{2}$ does not contain odd anti-holes of
length greater than five.

Now, a natural question is whether _perfectness_ is a partite testable
property (in general) or not. Note that a graph $G$ is perfect if and only if
it does not contain odd holes or odd anti-holes as induced subgraphs. As
mentioned above, the property of _not containing odd anti-holes of length
greater than five_ is a partite testable property for the squares of bipartite
graphs. However, the property of being _perfect_ fails to be a partite
testable property even for the squares of convex bipartite graphs, because
_(odd-hole)-freeness_ is not a partite testable property for the class of
squares of convex bipartite graphs. To see this, recall that for a convex
bipartite graph $G=(A,B,E)$, the subgraphs $G^{2}[A]$ and $G^{2}[B]$ are both
_interval graphs_ (a subclass of perfect graphs, and hence, (odd hole)-free)
[21], whereas the graph $G^{2}$ is _not necessarily (odd hole)-free_ and
hence, not always _perfect_ (see Figure 1).

On the other hand, we find some interesting subclasses of squares of convex
bipartite graphs for which _perfectness is a partite testable property_ (see
Theorem 8 and Theorem 7). Such a graph class includes _$C_{5}$ -free squares
of convex bipartite graphs_ (i.e. graphs $G^{2}$ such that $G^{2}$ is
$C_{5}$-free and $G$ is a convex bipartite graph). Further, we observe that
for the class of _$C_{4}$ -free squares of convex bipartite graphs_, even
_chordality is a partite testable property_. The above results are also
interesting due to the fact that the above subclasses are not hereditary. For
example, an induced subgraph of the square of a convex bipartite graph need
not be the square of a convex bipartite graph. Even though the notion of
perfectness is not just limited to hereditary graph classes, most of the well-
known classes of perfect graphs are hereditary. Theorem 7 contributes the
class of graphs, namely, _$C_{5}$ -free squares of convex bipartite graphs_ to
the rare collection of non-hereditary perfect graphs.

$a$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$b_{1}$$b_{2}$$v_{4}$ |  $a$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$b_{1}$$b_{2}$$v_{4}$
---|---
$G$ |  $G^{2}$
Figure 1: A convex bipartite graph, whose square is not perfect

###  1.2 Preliminaries

Given a graph $G=(V,E)$, a set of vertices $S\subseteq V(G)$ is said to be a
_clique_ in $G$ if they are pairwise adjacent in $G$. On the other hand, for a
set of vertices $S\subseteq V(G)$, if no two vertices in $S$ are adjacent in
$G$, then $S$ is said to be an _independent set_ in $G$. The square of a graph
$G=(V,E)$, denoted as $G^{2}$, is defined to be the graph with $V(G^{2})=V(G)$
and $E(G^{2})=\\{uv:uv\in E(G)$ or there exists a $w\in V(G)$ such that
$uw,wv\in E(G)\\}$. A graph $H$ is called an _induced subgraph_ of a graph $G$
if $V(H)\subseteq V(G)$ and $E(H)=\\{uv\in E(G):u,v\in V(H)\\}$; $H$ is then
also said to be the subgraph induced by $V(H)$. A _cycle_ in a graph $G$ is
defined as a sequence of disjoint vertices, denoted as $(v_{1},\ldots,v_{k})$
such that $\\{v_{i}v_{i+1}:1\leq i\leq k-1\\}\cup\\{v_{k}v_{i}\\}\subseteq
E(G)$. The length of a shortest cycle contained in a graph $G$ is called the
_girth_ of $G$. Let $C=(v_{0},v_{1},\ldots,v_{k-1})$ be a cycle in $G$. We say
that $P$ is a _sub-path_ of $C$ if there exist $i,j\in\\{0,1,2,\ldots,k-1\\}$
such that $P=(v_{i},v_{i+1},\ldots,v_{j})$ (indices modulo $k$) and
$v_{i}v_{j}\notin E(C)$. A _hole_ is defined as an induced cycle of length at
least four. The complement of a hole is called an _antihole_. A graph $G$ is
said to be _$H$ -free_ if $G$ does not contain $H$ as an induced subgraph. A
graph is said to be _chordal_ if it is hole-free. Let $H$ be a graph and
$\mathcal{C}$ be a graph class. By _$H$ -free squares of $\mathcal{C}$_, we
mean the graphs $G^{2}$ such that $G^{2}$ is $H$-free and $G\in\mathcal{C}$.

A graph $G$ is called a _bipartite graph_ if its vertices can be partitioned
into two disjoint independent sets $A$ and $B$ such that every edge in $G$ has
one endpoint in $A$ and the other endpoint in $B$. A bipartite graph with
partite sets $A$ and $B$ is usually denoted as _$G=(A,B,E)$_. A bipartite
graph is said to be _chordal bipartite_ if it does not contain any induced
cycle of length at least six. Note that chordal bipartite graphs form a
superclass of _convex bipartite graphs_ (see Definition 1). A graph $G$ is an
_interval graph_ if the vertices of $G$ can be represented by intervals on the
real line such that two vertices in $G$ are adjacent if and only if the
corresponding intervals intersect. The corresponding set of intervals is
called an interval representation of $G$. A _proper interval graph_ is an
interval graph that has an interval representation in which no interval
properly contains another. A graph $G$ is said to be _perfect_ if for each
induced subgraph $H$ of $G$, the chromatic number $\chi(H)=\omega(H)$, the
clique number. The well-known _Strong Perfect Graph Theorem_ states that _a
graph $G$ is perfect if and only if $G$ is both (odd hole)-free and (odd
antihole)-free_ [7]. Many graph families, including bipartite graphs, chordal
graphs, etc., are perfect.

Notation: For a vertex $v$ in a graph $G$, we denote by $N_{G}(v)$, the set of
vertices adjacent to $v$ in $G$ and $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. For a set
$S\subseteq V(G)$, we denote by $G[S]$, the subgraph induced by $S$. For
vertices $u,v\in V(G)$, we denote by $d_{G}(u,v)$, the distance (length of the
shortest path) between $u$ and $v$ in $G$. For a graph $G$ and $S\subseteq
V(G)$, we use $G-S$ to denote the graph $G[V(G)-S]$. For two graphs $G$ and
$H$, we denote by $G\cong H$ if $G$ and $H$ are isomorphic to each other.
Depending upon the context, sometimes we denote a cycle (path) of length $k$
as $(v_{1},\ldots,v_{k})$.

##  2 Observations on the asymptotic bounds

In this section, we derive some implications (Observations 1, 2, 4) of the
following upper and lower bounds for the chromatic numbers of squares of
graphs in the work of Alon and Mohar [2] stated below.

######  Theorem 2 ([2]).

  1. ($a$)

Let $\Delta\geq 2$ and $g\geq 7$ be any integers. There exists an absolute
constant $c_{1}$ such that for any graph $G$ with maximum degree $\Delta$ and
girth $g$ we have, $\chi(G^{2})\leq c_{1}\frac{\Delta^{2}}{\log\Delta}$.

  2. ($b$)

Let $\Delta\geq 2$ and $g\geq 7$ be any integers. There exist an absolute
constant $c_{2}$ and a graph $G$ with maximum degree $\Delta$, girth $g$, and
$\chi(G^{2})\geq c_{2}\frac{\Delta^{2}}{\log\Delta}$

Since we are interested in bounding $\chi(G^{2})$ in terms of $\omega(G^{2})$
(unlike in Theorem 2 where the bounds are in terms of the maximum degree,
$\Delta$ of $G$), for graphs having girth, $g\geq 7$, in the following lemma
we find a relation between the parameters maximum degree and clique number of
$G^{2}$.

######  Lemma 1.

Let $G$ be a graph with girth $g\geq 7$ and maximum degree $\Delta\geq 2$.
Then $\omega=\omega(G^{2})=\Delta+1$.

###### Proof.

Let $C$ be any maximum clique in $G^{2}$. Clearly, $|C|\geq\Delta+1$, as for
any vertex $v$ in $G$, the set $N_{G}[v]$ form a clique in $G^{2}$. Our goal
is to prove that $|C|\leq\Delta+1$ as well, which then proves the lemma. Note
that if there exists a vertex $v$ in $G$ such that $C\subseteq N_{G}[v]$, then
we are done. Suppose that no such vertex exists in $G$. i.e. $C\nsubseteq
N_{G}[v]$ for any vertex $v$ in $G$. Now, consider a vertex $a\in C$. Then, by
our assumption, there exists a vertex $b\in C$ such that $b\notin N_{G}[a]$.
Since $ab\in E(G^{2})$ (as $a,b\in C$), we have that there exists a vertex
$c\in V(G)$ such that $ac,bc\in E(G)$. As we also have $C\nsubseteq N_{G}[c]$,
there exists a vertex $x\in C$ such that $x\notin N_{G}[c]$. This implies that
$x\neq a,b,c$. Since $ax,bx\in E(G^{2})$ (as $a,b,x\in C$), at least one of
the following conditions should hold:

  1. 1.

$ax,bx\in E(G)$.

  2. 2.

$bx\in E(G)$, but $ax\notin E(G)$ and there exists a vertex $z$ in $G$ such
that $az,zx\in E(G)$.

  3. 3.

$ax\in E(G)$, but $bx\notin E(G)$ and there exists a vertex $y$ in $G$ such
that $by,yx\in E(G)$.

  4. 4.

$ax,bx\notin E(G)$, and there exist two vertices $y,z$ (possibly, $y=z$) in
$G$ such that $by,yx,az,zx\in E(G)$.

If (1) holds, we have a 4-cycle, namely, $(b,x,a,c)$ in $G$. Note that as
$cx\notin E(G)$, we have $c\neq y,z$. If either (2) or (3) hold, we have
5-cycles, namely, $(a,z,x,b,c)$ or $(b,y,x,a,c)$, respectively, in $G$ (note
that since $ab\notin E(G)$, we have $z\neq b$ and $y\neq a$). If (4) holds,
then we have a 6-cycle, namely, $(b,y,x,z,a,c)$ in $G$ when $y\neq z$, and a
4-cycle in $G$, namely $(b,y=z,a,c)$ when $y=z$. Therefore, in any case, we
have a contradiction to the fact that the girth, $g\geq 7$. Thus, we can
conclude that our assumption is not true. Hence the lemma. ∎

Now Observation 1 (respectively, Observation 2) follows from Theorem 2($a$)
(respectively, Theorem 2($b$)) and Lemma 1.

######  Observation 1.

Let $\omega\geq 3$ and $g\geq 7$ be any integers. There exists an absolute
constant $c_{1}$ such that for any graph $G$ with girth $g$ and
$\omega=\omega(G^{2})$, we have $\chi(G^{2})\leq
c_{1}\frac{(\omega-1)^{2}}{\log(\omega-1)}$.

######  Observation 2.

Let $\omega\geq 3$ and $g\geq 7$ be any integers. There exist an absolute
constant $c_{2}$ and a graph $G$ such that $G$ has girth $g$,
$\omega=\omega(G^{2})$, and $\chi(G^{2})\geq
c_{2}\frac{(\omega-1)^{2}}{\log(\omega-1)}$.

Interestingly, the tight example graph in Observation 2 can be converted to a
bipartite graph by using the following simple reduction. This further helps us
to prove the existence of bipartite graphs $B$ such that the chromatic number
of $B^{2}$ is $\Omega(\frac{\omega^{2}}{\log\omega})$, where $\omega$ is the
clique number of $B^{2}$.

Reduction: Given a graph $G$, we define a bipartite graph $B_{G}$ (which is
obtained by splitting each vertex of $G$) as follows:

$\displaystyle V(B_{G})$ $\displaystyle=A\cup B,\text{ where
}A=\\{u^{\prime}:u\in V(G\\}\text{ and }B=\\{u^{\prime\prime}:u\in V(G)\\}$
$\displaystyle E(B_{G})$
$\displaystyle=\\{u^{\prime}v^{\prime\prime}:u^{\prime}\in
A,v^{\prime\prime}\in B,\text{ such that either }u=v\text{ or }uv\in E(G)\\}$

We have the following lemma for the bipartite graph $B_{G}$, constructed by
the above reduction.

######  Lemma 2.

For any graph $G$, we have $B_{G}^{2}[A]\cong G^{2}$ and $B_{G}^{2}[B]\cong
G^{2}$.

###### Proof.

We only give the proof for $B_{G}^{2}[A]\cong G^{2}$, as similar arguments can
be used to prove $B_{G}^{2}[B]\cong G^{2}$. By the definition of $B_{G}$,
every vertex $u\in V(G^{2})$ corresponds to a vertex $u^{\prime}\in
V(B_{G}^{2}[A])$ (this provides us a bijective mapping from $V(G^{2})$ to
$V(B_{G}^{2}[A])$). It is now enough to show that for any two vertices $u,v\in
V(G^{2})$, we have $uv\in E(G^{2})$ if and only if $u^{\prime}v^{\prime}\in
E(B_{G}^{2}[A])$. Suppose that $uv\in E(G^{2})$. If $uv\in E(G)$, we then have
$u^{\prime}v^{\prime\prime},v^{\prime\prime}v^{\prime}\in E(B_{G})$, and
therefore, $u^{\prime}v^{\prime}\in E(B_{G}^{2}[A])$. If $uv\notin E(G)$, this
implies that there exists a vertex $w\in V(G)$ such that $uw,wv\in E(G)$. This
further implies that,
$u^{\prime}w^{\prime\prime},w^{\prime\prime}v^{\prime}\in E(B_{G})$, and
therefore $u^{\prime}v^{\prime}\in E(B_{G}^{2}[A])$. This proves the if part.
To prove the converse, assume that $u^{\prime}v^{\prime}\in E(B_{G}^{2}[A])$.
Since $B_{G}$ is a bipartite graph and both the vertices
$u^{\prime},v^{\prime}\in A$, this implies that there exists a vertex
$w^{\prime\prime}\in B$ such that
$u^{\prime}w^{\prime\prime},w^{\prime\prime}v^{\prime}\in E(B_{G})$. If either
$w^{\prime\prime}=u^{\prime\prime}$ or $w^{\prime\prime}=v^{\prime\prime}$, by
the definition of $B_{G}$, we then have $uv\in E(G)\subseteq E(G^{2})$.
Therefore, we can assume that $w^{\prime\prime}\neq
u^{\prime\prime},v^{\prime\prime}$. Then the fact that
$u^{\prime}w^{\prime\prime},w^{\prime\prime}v^{\prime}\in E(B_{G})$ implies
that $uw,wv\in E(G)$. This further implies that $uv\in E(G^{2})$, and we are
done. ∎

We note the following observation.

######  Observation 3.

For any graph $G$, we have $\omega(G^{2})\leq\omega(B_{G}^{2})\leq
2\omega(G^{2})$ and $\chi(G^{2})\leq\chi(B_{G}^{2})\leq 2\chi(G^{2})$.

###### Proof.

Clearly, $\omega(G^{2})\leq\omega(B_{G}^{2})$ and
$\chi(G^{2})\leq\chi(B_{G}^{2})$, as $G^{2}$ is present as an induced subgraph
in $B_{G}^{2}$ by Lemma 2. Since we have $B_{G}^{2}[A]\cong G^{2}$,
$B_{G}^{2}[B]\cong G^{2}$ (again, by Lemma 2), and
$V(B_{G}^{2})=V(B_{G}^{2}[A])\cup V(B_{G}^{2}[B])$, we have the remaining
inequalities,
$\omega(B_{G}^{2})\leq\omega(B_{G}^{2}[A])+\omega(B_{G}^{2}[B])=2\omega(G^{2})$
and $\chi(B_{G}^{2})\leq\chi(B_{G}^{2}[A])+\chi(B_{G}^{2}[B])=2\chi(G^{2})$. ∎

We now have Observation 4, which proves the existence of bipartite graphs
whose squares have a sub-quadratic lower bound for the chromatic number.

######  Observation 4.

Let $\omega^{\prime}\geq 3$. There exists an absolute constant $c$ and a
bipartite graph $H$ with $\omega(H^{2})\leq\omega^{\prime}$ and
$\chi(H^{2})\geq c\frac{(\omega(H^{2})-2)^{2}}{\log(\omega(H^{2})-1)}$.

###### Proof.

Let $g\geq 7$ and $\omega=\frac{\omega^{\prime}}{2}$. By Observation 2, there
exists an absolute constant $c_{2}$ and a graph $G$, with girth $g$ and
$\omega=\omega(G^{2})$ such that $\chi(G^{2})\geq
c_{2}\frac{(\omega-1)^{2}}{\log(\omega-1)}$. Let $H=B_{G}$ be the bipartite
graph obtained from $G$ by applying the above reduction. Then by Observation
3, we have that $\omega\leq\omega(H^{2})\leq 2\omega=\omega^{\prime}$. Again,
by Observation 3 and from the above inequalities, by setting $c=c_{2}/4$, we
have the following:

$\displaystyle\chi(H^{2})\geq\chi(G^{2})$ $\displaystyle\geq
c_{2}\frac{(\omega-1)^{2}}{\log(\omega-1)}$ $\displaystyle\geq
c_{2}\frac{(\frac{\omega(H^{2})}{2}-1)^{2}}{\log(\omega(H^{2})-1)}$
$\displaystyle\geq c\frac{(\omega(H^{2})-2)^{2}}{\log(\omega(H^{2})-1)}$

∎

##  3 Proof of Theorem 1

Let $G=(A,B,E)$ be a convex bipartite graph. Then by Definition 1, we have an
ordering, say $<_{B}$ for the vertices in $B$ such that, for each vertex $a\in
A$, the vertices in $N_{G}(a)$ appear consecutively with respect to $<_{B}$.
Now, consider the vertices in $B$ (with respect to the ordering $<_{B}$) as
points on the real line. Then, for each vertex $a\in A$, we define an interval
$I_{a}$ with $l(I_{a})=\min_{<_{B}}\\{b:b\in N_{G}(a)\\}$ and
$r(I_{a})=\max_{<_{B}}\\{b:b\in N_{G}(a)\\}$. Note that, for any two vertices
$a,a^{\prime}\in A$, $aa^{\prime}\in E(G^{2}[A])$ if and only if $I_{a}\cap
I_{a^{\prime}}\neq\emptyset$. Hence, the collection of intervals,
$\\{I_{a}\\}_{a\in A}$ is an interval representation of $G^{2}[A]$. We then
have the following observation, which is also noted in [21].

######  Observation 5 ([21]).

Let $G=(A,B,E)$ be a convex bipartite graph. Then the subgraph $G^{2}[A]$ is
an interval graph.

Moreover, it is also known that $G^{2}[B]$ is an interval graph [21]. But in
the following lemma, we prove a stronger observation for $G^{2}[B]$, which is
useful in proving some of our results. Note that for a graph $G$, an ordering
$<$ of $V(G)$ is called a _proper vertex ordering_ if for any three vertices
$u,v,w$ in $G$ such that $u<v<w$, $uw\in E(G)$ implies that $uv,vw\in E(G)$.
It is a well-known fact that the proper interval graphs are exactly those
graphs whose vertex set admits a proper vertex ordering.

######  Lemma 3.

Let $G=(A,B,E)$ be a convex bipartite graph. Then, the ordering $<_{B}$ of the
vertices in $B$ is a proper vertex ordering of $G^{2}[B]$. Consequently, the
subgraph $G^{2}[B]$ is a proper interval graph.

###### Proof.

Consider any three vertices, say $u,v,w\in B$, such that $u<_{B}v<_{B}w$.
Suppose that $uw\in E(G^{2})$. This implies that there exists a vertex $a\in
A$ such that $au,aw\in E(G)$. By the definition of $<_{B}$, $N_{G}(a)$ is
consecutive. Thus we have $av\in E(G)$. As $au,aw\in E(G)$, we can therefore
conclude that $uv,vw\in E(G^{2})$. This proves that $<_{B}$ is a proper vertex
ordering of vertices in $G^{2}[B]$. Hence, the observation. ∎

Now we define an ordering $<_{A}$ for the vertices in $A$ as follows: for any
pair of vertices, say $a_{i},a_{l}\in A$, we say that $a_{i}<_{A}a_{l}$ if and
only if $r(I_{a_{i}})\leq r(I_{a_{l}})$ (where $\\{I_{a}\\}_{a\in A}$ is the
same interval representation of $G^{2}[A]$ defined earlier, and if
$r(I_{a_{i}})=r(I_{a_{l}})$ we can have either $a_{i}<_{A}a_{l}$ or
$a_{l}<_{A}a_{i}$). In the remainder of the section, for a convex bipartite
graph $G=(A,B,E)$, we assume that the vertices of the sets $A$ and $B$ follow
the orderings $<_{A}$ and $<_{B}$ respectively. If $|A|=m$ and $|B|=n$, we
then denote $A=\\{a_{1},a_{2},\ldots,a_{m}\\}$, where
$a_{1}<_{A}\cdots<_{A}a_{m}$ and $B=\\{b_{1},b_{2},\ldots,b_{n}\\}$, where
$b_{1}<_{B}\cdots<_{B}b_{n}$. Throughout the section, we denote by $\omega$,
the size of the maximum clique of $G^{2}$. For vertices $x,y\in A$
(respectively, $x,y\in B$), the notation $x\leq_{A}y$ (respectively,
$x\leq_{B}y$) includes the possibility that $x=y$. We now infer the following
observations.

######  Observation 6.

Let $G=(A,B,E)$ be a bipartite graph. Let $a\in A$ and $b\in B$ be such that
$ab\in E(G^{2})$ then $ab\in E(G)$.

###### Proof.

Note that for $a\in A$ and $b\in B$, $d_{G}(a,b)\neq 2$. Therefore, by the
definition of $G^{2}$, $ab\in E(G^{2})$ implies that $ab\in E(G)$. ∎

######  Observation 7.

Let $a,a^{\prime}\in A$ be such that $a<_{A}a^{\prime}$, and $b,b^{\prime}\in
B$ be such that $b^{\prime}<_{B}b$. If $b\in N_{G}(a)$ and $b^{\prime}\in
N_{G}(a^{\prime})$ then $b\in N_{G}(a^{\prime})$.

###### Proof.

Since $a<_{A}a^{\prime}$, we have $r(I_{a})\leq r(I_{a^{\prime}})$. Now as
$b\in N_{G}(a)$, $b^{\prime}\in N_{G}(a^{\prime})$, $b^{\prime}<_{B}b$, and
the vertices in $N_{G}(a^{\prime})$ appear consecutive with respect to the
ordering $<_{B}$, we have $b\in N_{G}(a^{\prime})$. ∎

######  Observation 8.

For each $i\in\\{1,2,\ldots,m\\}$ and $j\in\\{1,2,\ldots,n\\}$, the sets
$N_{G^{2}}(a_{i})\cap\\{a_{i+1},\ldots,a_{m}\\}$ and
$N_{G^{2}}(b_{j})\cap\\{b_{j+1},\ldots,b_{n}\\}$ are both cliques in $G^{2}$.

###### Proof.

Let $b_{k}$ be the largest indexed vertex in
$N_{G^{2}}(b_{j})\cap\\{b_{j+1},\ldots,b_{n}\\}$. Since $b_{j}b_{k}\in
E(G^{2})$, there exists a vertex $a\in A$, such that $ab_{j},ab_{k}\in E(G)$.
Then, as vertices in $N_{G}(a)$ appear consecutively with respect to the
ordering $<_{B}$, we have that $ab_{l}\in E(G)$, for each $l$ such that $j\leq
l\leq k$. This implies that for any $l,l^{\prime}$ such that $j\leq
l,l^{\prime}\leq k$, we have $b_{l}b_{l^{\prime}}\in E(G^{2})$. Therefore,
$N_{G^{2}}(b_{j})\cap\\{b_{j+1},\ldots,b_{n}\\}$ is a clique in $G^{2}$.

Now suppose that $N_{G^{2}}(a_{i})\cap\\{a_{i+1},\ldots,a_{m}\\}$ is not a
clique in $G^{2}$. Then there exist vertices, $a_{k},a_{l}\in
N_{G^{2}}(a_{i})\cap\\{a_{i+1},\ldots,a_{m}\\}$ such that $a_{k}a_{l}\notin
E(G^{2})$. Without loss of generality, we can assume that $a_{k}<_{A}a_{l}$.
Then, by the definition of $<_{A}$, we have that $r(I_{a_{k}})\leq
r(I_{a_{l}})$. Recall that $\\{I_{a}\\}_{a\in A}$ is an interval
representation of $G^{2}[A]$. Since $a_{k}a_{l}\notin E(G^{2})$ and
$r(I_{a_{k}})\leq r(I_{a_{l}})$, we can infer that
$r(I_{a_{k}})<l(I_{a_{l}})$. As $a_{i}<_{A}a_{k}$, we then have
$r(I_{a_{i}})\leq r(I_{a_{k}})<l(I_{a_{l}})$. This further implies that
$a_{i}a_{l}\notin E(G^{2})$. This contradicts the fact that $a_{l}\in
N_{G^{2}}(a_{i})$. Hence, the observation. ∎

To prove the upper bound in Theorem 1, our idea is to recursively construct
subgraphs of $G^{2}$, namely, $H_{j}$, for each integer $j$ down from $n$ to
$1$, and show that the chromatic number of each of these subgraphs is bounded
by $\left\lfloor\frac{3\omega}{2}\right\rfloor$ (Lemma 4).

Subgraphs $H_{j}$: For each integer $j$ down from $n$ to $1$, we define an
induced subgraph $H_{j}=G^{2}[A\cup\\{b_{j},b_{j+1},\ldots,b_{n}\\}]$, where
the vertices in $A$ follows the ordering $<_{A}$, and
$b_{j}<_{B}b_{j+1}<_{B}\cdots<_{B}b_{n}$. Clearly, $H_{1}=G^{2}$, and
$G^{2}[A]$ is an induced subgraph of $H_{j}$ for each
$j\in\\{1,2,\ldots,n\\}$. Now, to prove the upper bound in Theorem 1, it is
enough to prove the following lemma.

######  Lemma 4.

For each $j\in\\{1,2,\ldots,n\\}$, we have
$\chi(H_{j})\leq\lfloor\frac{3\omega}{2}\rfloor$.

###  3.1 Some observations on subgraphs $H_{j}$

First, the following observation is immediate from the definition of $H_{j}$.

######  Observation 9.

Let $xy\in E(H_{j})\setminus E(H_{j+1})$ for some $j\in\\{1,2,\ldots,n-1\\}$.
Then either $x=b_{j}$ or $y=b_{j}$.

We have the following observation due to the definitions of $<_{A}$ and
$<_{B}$.

######  Observation 10.

For $j\in\\{1,2,\ldots,n\\}$, let $N_{H_{j}}(b_{j})\cap
A=\\{a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\\}$, where
$a_{i_{1}}<_{A}a_{i_{2}}<_{A}\cdots<_{A}a_{i_{k}}$. Then
$N_{H_{j}}(a_{i_{1}})\cap B\subseteq N_{H_{j}}(a_{i_{2}})\cap
B\subseteq\ldots\subseteq N_{H_{j}}(a_{i_{k}})\cap B$.

We also note the following.

######  Observation 11.

For $j\in\\{1,2,\ldots,n\\}$, let $A_{j}=N_{H_{j}}(b_{j})\cap A$ and
$B_{j}=N_{H_{j}}(b_{j})\cap B$. Then $|A_{j}|\leq\omega-1$ and
$|B_{j}|\leq\omega-2$.

###### Proof.

Let $A_{j}=N_{H_{j}}(b_{j})\cap A$. It is easy to see that
$A_{j}\cup\\{b_{j}\\}$ is a clique in $G^{2}$. This implies that
$|A_{j}|\leq\omega-1$. Let $B_{j}=N_{H_{j}}(b_{j})\cap
B=\\{b_{j_{1}},b_{j_{2}},\cdots,b_{j_{l}}\\}$, where
$b_{j_{1}}<_{B}b_{j_{2}}<_{B}\cdots<_{B}b_{j_{l}}$. By Observation 8, we have
that $B_{j}$ is a clique in $G^{2}$. Therefore, $B_{j}\cup\\{b_{j}\\}$ is also
a clique in $G^{2}$. Now, consider the vertex $b_{j_{l}}\in B_{j}$. As
$b_{j}b_{j_{l}}\in E(G^{2}[B])$, there exists a vertex $a\in A_{j}$ such that
$ab_{j},ab_{j_{l}}\in E(G)\subseteq E(G^{2})$. Then, by the definition of
$<_{B}$, we have that neighbors of $a$ are consecutive in $G$. Therefore, we
have $B_{j}\cup\\{b_{j}\\}\subseteq N_{G}(a)\subseteq N_{G^{2}}(a)$. This
implies that $B_{j}\cup\\{b_{j},a\\}$ is a clique in $G^{2}$. This further
implies that $|B_{j}|\leq\omega-2$. ∎

###  3.2 Proof of Lemma 4

Comment: We encourage the reader to go through the following proof jointly
with the algorithm described in Section 4 for a better understanding.

###### Proof.

The proof is based on reverse induction on the index $i$ of the subgraphs
$H_{i}$, $i\in\\{1,2,\ldots,n\\}$ defined above. For each
$i\in\\{1,2,\ldots,n\\}$, let

$A_{i}=N_{H_{i}}(b_{i})\cap A$ $B_{i}=N_{H_{i}}(b_{i})\cap B$

Recall that $G^{2}[A]$ is an interval graph (by Observation 5), and the size
of the maximum clique in $G^{2}[A]$ is at most $\omega$, where
$\omega=\omega(G^{2})$. Therefore, $G^{2}[A]$ is $\omega$-colorable. Consider
the base case, $i=n$. Note that $H_{n}=G^{2}[A\cup\\{b_{n}\\}]$ and
$B_{n}=\emptyset$. Also, by Observation 11, we have that
$|A_{n}|\leq\omega-1$. Therefore, as $G^{2}[A]$ is $\omega$-colorable, and
$|N_{H_{n}}(b_{n})|=|A_{n}|\leq\omega-1$, we can easily extend any
$\omega$-coloring of $G^{2}[A]$ to an $\omega$-coloring of $H_{n}$, and we are
done. Now, assume to the induction hypothesis that
$\chi(H_{j})\leq\lfloor\frac{3\omega}{2}\rfloor$ for any $j>i$. Consider
$H_{i}=G^{2}[A\cup\\{b_{n},b_{n-1},\ldots,b_{i}\\}]$. Our goal is to prove
that $\chi(H_{i})\leq\lfloor\frac{3\omega}{2}\rfloor$.

######  Definition 3 (Special coloring).

Any proper coloring of $H_{i+1}$ that uses at most
$\lfloor\frac{3\omega}{2}\rfloor$ colors is a special coloring of $H_{i+1}$.

Due to our induction hypothesis, a special coloring of $H_{i+1}$ always
exists. For a special coloring $c$ of $H_{i+1}$, if there exists a color, say
$x$, which is not used to color any vertex in $A_{i}\cup B_{i}$, then we can
extend the coloring $c$ to $H_{i}$ by assigning the color $x$ to $b_{i}$. This
would have proved the lemma.

Otherwise, if a special coloring $c$ of $H_{i+1}$ is not extendable, i.e. all
the $\lfloor\frac{3\omega}{2}\rfloor$ colors have been used up by the vertices
$A_{i}\cup B_{i}$, our intention is to convert $c$ to another special coloring
of $H_{i+1}$ by _Kempe changes_. i.e. _swapping_ the colors of some vertices.
Before that, we introduce some definitions and prove some properties for
_“non-extendable special colorings”_ of $H_{i+1}$.

######  Definition 4 (Non-extendable special coloring).

A special coloring $c$ of $H_{i+1}$ is “ _non-extendable_ ” if all the
$\lfloor\frac{3\omega}{2}\rfloor$ colors have been used up by the vertices in
$A_{i}\cup B_{i}$. Otherwise, $c$ is an extendable special coloring.

Claim 1. Let $c$ be a non-extendable special coloring. Then there exist
$\lfloor\frac{\omega}{2}\rfloor+2$ vertices in $A_{i}$ whose color (with
respect to $c$) is not assigned to any other vertex in $A_{i}\cup B_{i}$.

###### Proof.

Note that both the sets $A_{i}$ and $B_{i}$ are cliques in $H_{i}$ (due to the
fact $A_{i}=N_{G}(b_{i})\cap A$, and Observation 8). By Observation 11, we
have $|B_{i}|\leq\omega-2$. Since $c$ uses $\lfloor\frac{3\omega}{2}\rfloor$
colors in $A_{i}\cup B_{i}$, we then have that the vertices in $A_{i}$ use at
least $\lfloor\frac{\omega}{2}\rfloor+2$ extra colors which are not used for
coloring any of the vertices in $B_{i}$. This proves the claim (since $A_{i}$
is a clique, no two vertices in $A_{i}$ can have the same color). ∎

######  Definition 5.

For a non-extendable special coloring $c$ of $H_{i+1}$, let
$a_{c}=\min_{<A}\\{a\in A_{i}:$ the color $c(a)$ is not used by any other
vertex in $A_{i}\cup B_{i}\\}$. We call $a_{c}$ the pivot vertex with respect
to $c$.

Note that the pivot vertex $a_{c}$ is well defined for any non-extendable
special coloring $c$ of $H_{i+1}$, by Claim 3.2. Now Claim 3.2 is immediate
from Claim 3.2 and the definition of $a_{c}$.

Claim 2. For a non-extendable special coloring $c$ of $H_{i+1}$, let
$A_{i}^{\prime}=\\{a\in A_{i}:a_{c}\leq_{A}a$}. Then
$|A_{i}^{\prime}|\geq\Big{\lfloor}\frac{\omega}{2}\Big{\rfloor}+2$.

Claim 3. For a non-extendable special coloring $c$ of $H_{i+1}$, one of the
following holds:

  1. ($a$)

There are $\Big{\lfloor}\frac{3\omega}{2}\Big{\rfloor}$ vertices in
$N_{H_{i+1}}[a_{c}]$, all receiving distinct colors with respect to $c$, or

  2. ($b$)

There exists an extendable special coloring $c^{\prime}$ of $H_{i+1}$.

###### Proof.

Suppose ($a$) is not true, then there exists a color, say
$x\in\\{1,2,\ldots,\lfloor\frac{3\omega}{2}\rfloor\\}$, such that $x\neq
c(a_{c})$, and the color $x$ is not used by any neighbor of $a_{c}$. Then, let
$c^{\prime}$ be a coloring of $H_{i+1}$ such that $c^{\prime}(v)=c(v)$ for
each vertex $v\neq a_{c}$, and $c^{\prime}(a_{c})=x$. Clearly, $c^{\prime}$ is
a special coloring of $H_{i+1}$ and it is also extendable, since with respect
to the coloring $c^{\prime}$, the vertex $b_{i}$ can now be assigned with the
color $c(a_{c})$ to obtain a
$\Big{\lfloor}\frac{3\omega}{2}\Big{\rfloor}$-coloring of $H_{i}$. This
implies ($b$) is true, and hence the claim. ∎

For a non-extendable special coloring $c$ of $H_{i+1}$, if Claim 3.2($b$) is
true, then we are done. Therefore, the difficult case is when Claim 3.2($a$)
is true, but not 3.2($b$).

Claim 4. For a non-extendable special coloring $c$ of $H_{i+1}$, let 3.2($a$)
is true. Then there exists a color
$y\in\Big{\\{}1,2,\ldots,\Big{\lfloor}\frac{3\omega}{2}\Big{\rfloor}\Big{\\}}$
such that $y\neq c(a_{c})$, and the color $y$ is not assigned to any vertex of
the set,

$S=(N_{H_{i+1}}(a_{c})\cap B)\cup\\{a\in(N_{H_{i+1}}(a_{c})\cap
A):a_{c}<_{A}a\\}$

(Note that $S$ is exactly the set obtained from $N_{H_{i+1}}(a_{c})$, by
deleting the vertices that lies before $a_{c}$ in the ordering $<_{A}$)

###### Proof.

Let $S_{1}=N_{H_{i+1}}(a_{c})\cap B$ and $S_{2}=\\{a\in(N_{H_{i+1}}(a_{c})\cap
A):a_{c}<_{A}a\\}$. Then $S=S_{1}\cup S_{2}$. Let $A_{i}^{\prime}=\\{a\in
A_{i}:a_{c}\leq_{A}a$} (as in the statement of Claim 3.2). Then by Observation
10, we have that $S_{1}\subseteq(N_{H_{i}}(a)\cap B)$ for each vertex $a\in
A_{i}^{\prime}$. This implies that $A_{i}^{\prime}\cup S_{1}\cup\\{b_{i}\\}$
form a clique in $H_{i}$. This further implies that $|A_{i}^{\prime}\cup
S_{1}\cup\\{b_{i}\\}|\leq\omega$. Since
$|A_{i}^{\prime}|\geq\Big{\lfloor}\frac{\omega}{2}\Big{\rfloor}+2$ (by Claim
3.2), we then have $|S_{1}\cup\\{bi\\}|\leq\lceil\frac{\omega}{2}\rceil-2$.
This implies that $|S_{1}|\leq\lceil\frac{\omega}{2}\rceil-3$. Note that
$\lfloor\frac{3\omega}{2}\rfloor-1$ colors are used in $N_{H_{i+1}}(a_{c})$
(since 3.2($a$) is true). i.e. the set
$N_{H_{i+1}}(a_{c})=(N_{H_{i+1}}(a_{c})\cap A)\cup S_{1}$ uses
$\lfloor\frac{3\omega}{2}\rfloor-1$ colors. Therefore, as
$|S_{1}|\leq\lceil\frac{\omega}{2}\rceil-3$, we can conclude that the set
$N_{H_{i+1}}(a_{c})\cap A$ uses at least $\omega+1$ colors that is not used in
$S_{1}$. Now as the set $\\{a_{c}\\}\cup S_{2}$ form a clique (by Observation
8), we have that the set $S_{2}$ can use only at most $\omega-1$ colors.
Therefore, the fact that $N_{H_{i+1}}(a_{c})\cap A$ uses at least $\omega+1$
colors implies that there exists a vertex, say $a\in(N_{H_{i+1}}(a_{c})\cap
A)$ such that $a<_{A}a_{c}$ and $y=c(a)\neq c(v)$ for any vertex $v\in
S_{1}\cup S_{2}\cup\\{a_{c}\\}$. This proves the claim. ∎

Let $c$ be a non-extendable special coloring of $H_{i+1}$ for which 3.2($a$)
is true. Then by Claim 3.2, there exists a color
$y\in\\{1,2,\ldots,\lfloor\frac{3\omega}{2}\rfloor\\}$ such that $y\neq
c(a_{c})$, and the color $y$ is not assigned to any vertex of the set

$S=(N_{H_{i+1}}(a_{c})\cap B)\cup\\{a\in(N_{H_{i+1}}(a_{c})\cap
A):a_{c}<_{A}a\\}$

Let $x=c(a_{c})$. Recall that $a_{c}$ is called as the _pivot vertex_ with
respect to $c$. In the rest of the section, with respect to the coloring $c$,
we call $x$ the _pivot color_ , and $y$ the _partner color_. Define,
$X=\\{v\in V(H_{i+1}):c(v)=x\\}$ and $Y=\\{v\in V(H_{i+1}):c(v)=y\\}$. Let $D$
denote the component of the induced subgraph $H_{i+1}[X\cup Y]$ that contains
the pivot vertex $a_{c}$. We call $D$ the _Kempe component (defined by the
pivot and partner colors) containing the pivot_ with respect to the coloring
$c$. In the claim below, we evaluate the properties of this Kempe Component.
In particular, we intend to prove that $D$ is completely contained in the set
$A$. Moreover, we will see that the vertices in the Kempe component containing
the pivot vertex and partners are arranged in $A$ in a specific order.

Claim 5. Let $c$ be a non-extendable special coloring of $H_{i+1}$, for which
3.2($a$) is true and let $D$ be the Kempe component (defined by the pivot and
partner colors) containing the pivot with respect to $c$. For each $l\geq 0$,
let $V_{l}=\\{v\in V(D):d_{H_{i}}(v,a_{c})=l\\}$, where $V_{0}=\\{a_{c}\\}$.
Then, the following conditions hold.

  1. ($a$)

For each $l\geq 0$, we have $V_{l}\subseteq A$. Moreover, for any pair of
vertices $v\in V_{l+1}$, $u\in V_{l}$ such that $uv\in E(H_{i+1})$, we have
$v<_{A}u$.

  2. ($b$)

For each $l\geq 2$, we have $N(b)\cap V_{l}=\emptyset$ for any
$b\in(V(H_{i})\cap B)$, .

###### Proof.

For the sake of contradiction, assume that the claim is not true. Let
$k=\min\\{l:l\geq 0\\}$, such that our claim is not true (i.e. for any $l<k$,
the Part ($a$) holds if $l\geq 0$, and the Part ($b$) holds if $l\geq 2$).

Note that $k\neq 1$, since $V_{0}$ has only the pivot vertex $a_{c}$ in it,
and by the definition of partner color $y$, we have
$V_{1}\subseteq\\{a\in(N_{H_{i+1}}(a_{c})\cap A):a<_{A}a_{c}\\}$.

Suppose that $k=2$.

Part ($a$) for $k=2$: Let $v\in V_{2}$. Then there exists a vertex $u\in
V_{1}$ such that $uv\in E(H_{i+1})$, $c(u)=y$, and $c(v)=c(a_{c})=x$. (Note
that the colors on the vertices belonging to the sets $V_{l}$ and $V_{l+1}$
alternate between $x$ and $y$ for each $l\geq 0$.) Recall that $x=c(a_{c})$ is
not assigned to any other vertex in $N_{H_{i}}(b_{i})=A_{i}\cup B_{i}$. As
$u<_{A}a_{c}$, $a_{c}\in N_{H_{i}}(b_{i})$, and $b_{i}$ is the least indexed
vertex in $V(H_{i})\cap B$, we then have by the definition of $<_{A}$ that,
$(N_{H_{i}}(u)\cap B)\subseteq(N_{H_{i}}(a_{c})\cap B)\subseteq B_{i}$. Now,
since $v\in N_{H_{i}}(u)$ and $c(v)=x$, we can conclude that $v\notin B$.
Therefore, $v\in A$. To show that the Part ($a$) is true for $k=2$, now it is
enough to prove that $v<_{A}u$. Assume to the contrary that $u<_{A}v$. Since
$a_{c},v\in N_{H_{i}}(u)$ and $u<_{A}a_{c},v$, we then have by Observation 8
that $va_{c}\in E(H_{i+1})$. As $c(v)=c(a_{c})=x$, this contradicts the fact
that $c$ is a proper coloring of $H_{i+1}$. Thus, we can conclude that
$v<_{A}u<_{A}a_{c}$. Therefore, Part ($a$) is true for $k=2$.

Part ($b$) for $k=2$: Recall that $v<_{A}a_{c}$, $a_{c}\in N_{H_{i}}(b_{i})$,
and $b_{i}$ is the least indexed vertex in $V(H_{i})\cap B$. We then have that
$(N_{H_{i}}(v)\cap B)\subseteq N_{H_{i}}(a_{c})$ (by the definition of
$<_{A})$. Thus, if $vb\in E(H_{i})$ for some $b\in V(H_{i})\cap B$, we then
have $va_{c}\in E(H_{i})$ and therefore, $va_{c}\in E(H_{i+1})$ by Observation
9. As $c(v)=c(a_{c})=x$, this again contradicts the fact that $c$ is a proper
coloring of $H_{i+1}$. Therefore, Part ($b$) is also true for $k=2$ .

Thus, we can conclude that our claim is true for $k=2$, and hence we can
assume that $k>2$.

Part ($a$) for $k>2$: Let $v\in V_{k}$. Then there exists a vertex $u\in
V_{k-1}$, $w\in V_{k-2}$ such that $vu,uw\in E(H_{i+1})$, and $c(w)=c(v)$.
Note that $k-1\geq 2$, and therefore, by the minimality of $k$, we have that
($b$) is true for $k-1$. Since $u\in V_{k-1}$, we then have that $ub\notin
E(H_{i})$ for any $b\in V(H_{i})\cap B$. As $uv\in E(H_{i+1})\subseteq
E(H_{i})$, this implies that $v\notin B$. Therefore, we can conclude that
$V_{k}\subseteq A$. Now, suppose that $u<_{A}v$. Again, by the minimality of
$k$, we have that ($a$) is true for $k-1$. Since $u\in V_{k-1}$ and $w\in
V_{k-2}$ are such that $uw\in E(H_{i+1})$, this implies that $u<_{A}w$. This
further implies that $u<_{A}v,w$. By Observation 8, we then have that $vw\in
E(H_{i+1})$. As $c(v)=c(w)=x$, this contradicts the fact that $c$ is a proper
coloring of $H_{i+1}$. Thus, we can conclude that $v<_{A}u$. This proves that
the Part ($a$) is true for $k$.

Part ($b$) for $k>2$: Since $v<_{A}u$, we also have $r(I_{v})\leq r(I_{u})$
(by the definition of $<_{A}$). Recall that $u\in V_{k-1}$ and Part ($b$)
holds for $k-1$. Therefore, the fact that $ub\notin E(H_{i})$ for any $b\in
V(H_{i})\cap B$ implies that $vb\notin E(H_{i})$ for any $b\in V(H_{i})\cap
B$. This proves that Part ($b$) is also true for $k$.

Our claim is true as we have a contradiction for the existence of $k$. ∎

Now define a new proper coloring, say $\phi_{c}$ of $H_{i+1}$ obtained from
$c$ by _swapping the pivot color and partner color on the vertices belonging
to the Kempe component $D$_. Formally, it can be defined as follows:

$\phi_{c}(v)=\begin{cases}c(v),&v\in V(H_{i+1})\setminus D\\\ x,&v\in D\cap
Y\\\ y,&v\in D\cap X\end{cases}$

Clearly, $\phi_{c}$ is a special coloring of $H_{i+1}$, and for every non-
extendable special coloring, $c$ of $H_{i+1}$ for which 3.2($a$) is true,
$\phi_{c}$ exists. If $\phi_{c}$ is an extendable special coloring for
$H_{i+1}$, then we are done. Otherwise, in the following claim, we prove _a
strictly decreasing property of the pivot vertex in the modified special
coloring $\phi_{c}$_. As the number of vertices in the graph is finite, this
claim guarantees that we will finally end up having a coloring, say $c^{*}$,
for which $\phi_{c^{*}}$ is an extendable special coloring.

Claim 6. Let $c$ be a non-extendable special coloring of $H_{i+1}$ for which
3.2($a$) is true. If $\phi_{c}$ is non-extendable in $H_{i+1}$ then
$a_{\phi_{c}(v)}<_{A}a_{c}$.

###### Proof.

Recall that $\phi_{c}$ is a special coloring of $H_{i+1}$ and
$\phi_{c}(a_{c})=y$. If $\phi_{c}$ is non-extendable in $H_{i+1}$, we then
have that all the $\Big{\lfloor}\frac{3\omega}{2}\Big{\rfloor}$ colors are
used in the set $A_{i}\cup B_{i}$ with respect to the special coloring
$\phi_{c}$. In particular, now there exists a vertex, say $v\in(A_{i}\cup
B_{i})\setminus\\{a_{c}\\}$ that has the color $x$ on it. i.e. $\phi_{c}(v)=x$
but $c(v)\neq x$. Since we have recolored only the vertices in the Kempe
component $D$ (containing the pivot and partners with respect to $c$) to
obtain the new coloring $\phi_{c}$ from $c$, this implies that $v\in
D\subseteq A$, $v<_{A}a_{c}$ (by Claim 3.2($a$)), and $c(v)=y$. Moreover, with
respect to the coloring $\phi_{c}$, no vertex in $B_{i}$ has been colored $x$
(since $D\subseteq A$ by Claim 3.2($a$)). Also, since $A_{i}$ is a clique, $v$
is the only vertex in $A_{i}\cup B_{i}$ that has the color $x$ on it.
Therefore, we now have a coloring $\phi_{c}$ of $H_{i+1}$ with the property
that there exists a vertex $v\in A_{i}$, $v<_{A}a_{c}$ such that
$\phi_{c}(v)=x$, and the color $x$ is not assigned to any other vertex in
$A_{i}\cup B_{i}$. By the definition of the pivot vertex with respect to
$\phi_{c}$, we then have $a_{\phi_{c}}\leq_{A}v$. Further, $v<_{A}a_{c}$
implies that $a_{\phi_{c}}<_{A}a_{c}$. Therefore, our claim is true. ∎

Now, we are ready to conclude the proof of Lemma 4. If there is an extendable
special coloring for $H_{i+1}$, then we are done. Suppose that there does not
exist an extendable special coloring for $H_{i+1}$. Let $c^{*}$ be a non-
extendable special coloring of $H_{i+1}$ having the property that, for any
non-extendable special coloring $c$ of $H_{i+1}$ different from $c^{*}$, we
have $a_{c^{*}}\leq_{A}a_{c}$. Clearly, 3.2($a$) is true for $c^{*}$. But then
by Claim 3.2, we have $a_{\phi_{c^{*}}(v)}<_{A}a_{c^{*}}$. This is a
contradiction to the choice of $c^{*}$. This completes the proof of Lemma 4. ∎

The existence of convex bipartite graphs $H$ with
$\chi(H^{2})\geq\frac{5\omega(H^{2})}{4}-2$ is proved below. This completes
the proof of Theorem 1.

####  3.2.1 Lower bound construction

For the graph $H$ in Figure 2, for each $i\in\\{1,2,\ldots,5\\}$, the set
$Q_{i}$ represents a clique on $q$ vertices. For distinct
$i,j\in\\{1,2,\ldots,5\\}$ an edge connecting the sets $Q_{i}$ and $Q_{j}$
indicates the presence of all edges of the form $q_{i}q_{j}$, where $q_{i}\in
Q_{i}$ and $q_{j}\in Q_{j}$, and for $k\in\\{1,2,3\\}$, an edge connecting a
vertex $z_{k}$ and a set $Q_{i}$ indicates the presence of all edges of the
form $z_{k}q_{i}$, where $q_{i}\in Q_{i}$. The graph $H$ shown in Figure 2 is
a convex bipartite graph because, as shown in Figure 2, the vertices in $B$
with an ordering $<_{B}$: $Q_{2}<_{B}z_{2}<_{B}z_{3}<_{B}Q_{3}$ (where
vertices in the sets $Q_{2}$ and $Q_{3}$ can be ordered arbitrarily among
themselves) satisfies the consecutive property in the definition of a convex
bipartite graph. Since the set $B=Q_{2}\cup\\{z_{2},z_{3}\\}\cup Q_{3}$ form a
clique in $H^{2}$, we have $\omega(H^{2})=2q+3$. The structure of the induced
subgraph, $H^{\prime}=H^{2}[\bigcup_{i=1}^{5}Q_{i}]$ is commonly known as the
“blow-up” of a 5-cycle. It can be seen that $\chi(H^{\prime})=\frac{5}{2}q$,
and therefore it is not difficult to verify that,
$\chi(H^{2})=\frac{5}{2}q+2=\frac{5(\omega(H^{2})-3)}{4}+2\geq\frac{5}{4}\omega(H^{2})-2$.

…$q$…$q$…$q$$z_{1}$…$q$$z_{2}$$z_{3}$…$q$$Q_{1}$$Q_{2}$$Q_{5}$$Q_{4}$$Q_{3}$ |  …$q$…$q$…$q$$z_{1}$…$q$$z_{2}$$z_{3}$…$q$$Q_{1}$$Q_{2}$$Q_{5}$$Q_{4}$$Q_{3}$
---|---
$H$ |  $H^{2}$
Figure 2: A convex bipartite graph $H$ with $\omega(H^{2})=2q+3$ and
$\chi(H^{2})=\frac{5}{2}q+2$

##  4 A $\frac{3}{2}$-approximation algorithm

Here, we propose a polynomial-time algorithm to find a proper coloring for
squares of convex bipartite graphs using at most $3\omega/2$ colors (which is
the same as the $\chi$-binding function proved in Theorem 1).

Let $G=(A,B,E)$ be a convex bipartite graph. Recall the definitions of
orderings $<_{A}$ and $<_{B}$. Note that the convexity property of $G$ is the
well-known _“consecutive-ones”_ property when $G$ is represented as an
adjacency matrix. Hence, the ordering $<_{B}$ of the vertices of $B$ can be
obtained by using an $O(|V|+|E|)$-time algorithm proposed by Booth and Lueker
[4]. For ordering the vertices of $A$ with respect to $<_{A}$, we can use the
_“compact representation”_ of $G$ [18], which can be computed in $O(|V|+|E|)$
time. In the compact representation of $G$, for each vertex $i\in A$, we have
a triple $(i,\textit{left}(i),\textit{right}(i))$, where $\textit{left}(i)$
and $\textit{right}(i)$ are the least indexed and highest indexed neighbors of
$i$ in $B$. Consequently, the collection of intervals
$\\{[\textit{left}(i),\textit{right}(i)]:i\in A\\}$ forms a valid interval
representation of the interval graph $G^{2}[A]$ (by Observation 5). For
$j\in\\{1,2,\ldots,n\\}$, recall the definitions of subgraphs $H_{j}$ of
$G^{2}$. Our algorithm consists of two phases. First, we find a proper
coloring of the interval graph $G^{2}[A]$ using the well-known greedy coloring
algorithm [12]. In the second phase, for each $j$ down from $n$ to $1$, we
iteratively find a proper coloring for the subgraphs $H_{j}$ of $G^{2}$ using
at most $3\omega/2$ colors. Since $H_{1}=G^{2}$, we then have the desired
coloring of $G^{2}$.

### The algorithm

Phase I. Find a proper coloring, say $c$ of $G^{2}[A]$ using the greedy
algorithm.

Comment: Clearly, $c$ uses at most $\omega$ colors. Let $H_{n+1}=G^{2}[A]$ and
$j\in\\{1,2,\ldots,n\\}$. For a non-extendable special coloring $c$ of
$H_{j+1}$, recall the definitions of _the pivot vertex, the pivot color, the
partner color, the Kempe component containing pivot and partners, and the
recoloring $\phi_{c}$_ from the previous section. Moreover, in the following
phase of the algorithm, we say that $w$ is a _free color_ in $S\subseteq V(G)$
with respect to a coloring $c$ of $H_{j+1}$ if
$w\in\\{1,2,\ldots,\lfloor\frac{3\omega}{2}\rfloor\\}$ and $c(u)\neq w$ for
any $u\in S$.

Phase II. | For | each |  $j$ | down from $n$ to $1$ do the | following:
---|---|---|---|---|---
| 1\. Consider the coloring $c$ of $H_{j+1}$.
| 2\. If there is a free color, say $w$ in $N_{H_{j}}(b_{j})\subseteq
V(H_{j+1})$ with respect to $c$,
|  | then assign $c(b_{j})=w$.
| 3\. Else, find the _pivot vertex_ $a_{c}$ with respect to $c$. Let
$c(a_{c})=x$.
|  | 3.1. If there is a free color, say $z$ in $N_{H_{j+1}}[a_{c}]$,
|  |  | then assign $c(a_{c})=z$ and $c(b_{j})=x$.
|  | 3.2. Else, let $y$ be the _partner color_ of $a_{c}$.
|  |  (i) Find the lowest indexed vertex, say $a^{\prime}$ in $N_{H_{j+1}}(a_{c})\cap A$ such that
|  |  |  |  $a^{\prime}<_{A}a_{c}$ and $c(a^{\prime})=y$.
|  |  (ii) Swap the colors in the _Kempe component (defined by the pivot and_
|  |  |  |  _partner colors) containing the pivot_ ; i.e. set $c=\phi_{c}$.
|  |  (iii) If $a^{\prime}\notin N_{H_{j}}(b_{j})$ then $c(b_{j})=x$.
|  |  (iv) Else, $a^{\prime}$ is the new pivot vertex with respect to $c$ with $c(a^{\prime})=x$;
|  |  |  |  set $a_{c}=a^{\prime}$ and goto 3.1.

The above algorithm may not produce an optimal coloring, but the proof of
Lemma 4 guarantees that the algorithm terminates after finite steps and
outputs a proper coloring of $G^{2}$ using at most $3\omega/2$ colors in
polynomial time. To be specific, we note the following:

For each $j\in\\{1,2,\ldots,n\\}$, $c$ is a special coloring of $H_{j+1}$.
Therefore, _if step 2 is not true_ then it implies that $c$ is a non-
extendable special coloring of $H_{j+1}$ (see Definition 4). Thus, by Claim
3.2, the pivot vertex $a_{c}$ exists, and it is easy to see that $a_{c}$ can
be found in polynomial time. Now, _if step 3.1 is not true_ then it implies
that Claim 3.2($a$) is true. Therefore, by Claim 3.2, the partner color $y$
exists. Also, the steps 3.2.(i) and 3.2.(ii) can be executed in polynomial
time. Note that for fixed $j$, the repetition of step 3.1 only happens when
step 3.2.(iii) is not true (i.e. $a^{\prime}\in N_{H_{j}}(b_{j})$). Moreover,
in this case, the new pivot vertex $a^{\prime}$ obtained in step 3.2.(iv) has
the property that $a^{\prime}<a_{c}$, where $a_{c}$ is the current pivot
vertex. Therefore, step 3 will be executed at most $|N_{H_{j}}(b_{j})\cap A|$
times.

Let ${OPT}$ denote the number of colors used in an optimal coloring of
$G^{2}$. Clearly, ${OPT}\geq\omega$. Since our algorithm uses only at most
$3\omega/2\leq\frac{3}{2}OPT$ colors, we have the following theorem.

######  Theorem 3.

There exists a polynomial-time algorithm to find a proper coloring of squares
of convex bipartite graphs with approximation ratio $\frac{3}{2}$.

##  5 Relation with maximum degree

In this section, we prove the following theorem.

######  Theorem 4.

Let $G$ be a convex bipartite graph with maximum degree, $\Delta\geq 1$. Then
$\chi(G^{2})\leq 2\Delta$. Moreover, there exist convex bipartite graphs $G$
with $\chi(G^{2})=2\Delta$.

Let $G=(A,B,E)$ be a complete bipartite graph with $|A|=|B|=n$. Clearly, $G$
is a convex bipartite graph with maximum degree $n$, and $G^{2}$ is a clique
on $2n$ vertices. Thus we have $\chi(G^{2})=2n$. This shows that the class of
regular complete bipartite graphs form an instance of the graphs for which
$\chi(G^{2})=2\Delta$, where $\Delta$ is the maximum degree of $G$. This
proves the latter part of Theorem 4. In the remaining part of this section, we
work towards proving the former part of Theorem 4.

First, we note the following observation.

######  Observation 12.

Let $G$ be a convex bipartite graph with orderings $<_{A}$ and $<_{B}$ (as
defined earlier). Let $C_{A}$ be a clique in $G^{2}[A]$ and let $C_{B}$ be a
clique in $G^{2}[B]$. Then there exists vertices $a\in A$ and $b\in B$, such
that $C_{A}\subseteq N_{G}(b)$ and $C_{B}\subseteq N_{G}(a)$.

###### Proof.

Let $C_{A}$ be a clique in $G^{2}[A]$ with $|C_{A}|=p$ for some integer $p\geq
1$. Then, we can denote $C_{A}=\\{a_{i_{1}},a_{i_{2}},\ldots,a_{i_{p}}\\}$,
where $a_{i_{1}}<_{A}a_{i_{2}}<_{A}\cdots<_{A}a_{i_{p}}$. Let $b\in B$ be the
neighbor of $a_{i_{1}}$ in $G$ that has a maximum index with respect to the
ordering $<_{B}$. i.e. $b=\max_{<_{B}}\\{b_{l}:b_{l}\in N_{G}(a_{i_{1}})\\}$.
Let $a\in C_{A}\setminus\\{a_{i_{1}}\\}$. Since $C_{A}$ is a clique in
$G^{2}[A]$, we have $a_{i_{1}}a\in E(G^{2})$. This implies that
$N_{G}(a_{i_{1}})\cap N_{G}(a)\neq\emptyset$. Since $a_{i_{1}}<_{A}a$, by the
definitions of $<_{A}$ and $b$, we then have $b\in N_{G}(a)$. This implies
that $C_{A}\subseteq N_{G}(b)$.

Let $C_{B}$ be a clique in $G^{2}[B]$ with $|C_{B}|=q$ for some integer $q\geq
1$. Then we can denote $C_{B}=\\{b_{j_{1}},b_{j_{2}},\ldots,b_{j_{q}}\\}$,
where $b_{j_{1}}<_{B}b_{j_{2}}<_{B}\cdots<_{B}b_{j_{q}}$. Since
$b_{j_{1}}b_{j_{q}}\in E(G^{2})$, there exists a vertex $a\in A$ such that
$b_{j_{1}},b_{j_{q}}\in N_{G}(a)$. By the consecutive property of the ordering
$<_{B}$, we then have
$C_{B}=\\{b_{j_{1}},b_{j_{2}},\ldots,b_{j_{q}}\\}\subseteq N_{G}(a)$. ∎

We are now ready to prove Theorem 4.

Proof of Theorem 4

###### Proof.

Let $\omega_{A}$ and $\omega_{B}$ denote the size of maximum cliques in
$G^{2}[A]$ and $G^{2}[B]$ respectively. Then by Observation 12, we have that
$\omega_{A}\leq\Delta$ and $\omega_{B}\leq\Delta$. Recall that $G^{2}[A]$ is
an interval graph by Observation 5, and $G^{2}[B]$ is a proper interval graph
by Lemma 3. As both the subgraphs $G^{2}[A]$ and $G^{2}[B]$ are perfect, we
then have $\chi(G^{2}[A])=\omega_{A}\leq\Delta$ and
$\chi(G^{2}[B])=\omega_{B}\leq\Delta$. Therefore, we can conclude that
$\chi(G^{2})\leq\chi(G^{2}[A])+\chi(G^{2}[B])\leq 2\Delta$. This completes the
proof of Theorem 4.

∎

##  6 On partite testable properties

Here, we present a few structural observations on the squares of bipartite
graphs when some special properties are satisfied. In particular, we
investigate some _partite testable properties_ (see Definition 2) for the
squares of bipartite graphs.

######  Theorem 5.

The property of not containing odd anti-holes of size larger than five is a
partite testable property for the squares of bipartite graphs.

###### Proof.

Let $G=(A,B,E)$ be a bipartite graph with partite independent sets $A$ and
$B$. Suppose that both the subgraphs $G^{2}[A]$ and $G^{2}[B]$ do not contain
odd anti-holes of size larger than five. We need to prove that $G^{2}$ also
satisfies the same property. For the sake of contradiction, suppose that
$G^{2}$ has an odd anti-hole, say $H$, of size larger than five. Let
$V(H)=\\{v_{0},v_{1},\ldots,v_{k}\\}$, where $k$ is even, $k\geq 6$; here, the
vertices are labeled with respect to the cyclic order of the vertices in its
complement, which is a hole. (Throughout the proof, we consider the indices
modulo $k+1$). Note that by the definition of an anti-hole, for each
$i\in\\{0,1,2,\ldots,k\\}$, we have
$N_{H}(v_{i})=V(H)\setminus\\{v_{i-1},v_{i+1}\\}$. In other words, any two
vertices that are non-adjacent in $H$ are consecutive with respect to their
labeling.

We now have the following claims.

Claim 7. There exists $i\in\\{0,1,\ldots,k\\}$ such that $v_{i},v_{i+1}\in A$
or $v_{i},v_{i+1}\in B$

###### Proof.

Suppose not. Without loss of generality, we can assume that $v_{0}\in A$. For
$i\in\\{0,1,\ldots,k\\}$, we then have $v_{i}\in A$, if $i$ is even and
$v_{i}\in B$, if $i$ is odd. As $k$ is even, this implies that $v_{0},v_{k}\in
A$. Since $v_{k+1}=v_{0}$, this is a contradiction to our assumption. Hence,
the claim. ∎

Claim 8. For $i\in\\{0,1,\ldots,k\\}$, if $v_{i},v_{i+1}\in A$ (respectively,
$B$) then $N_{H}(v_{i})\cap N_{H}(v_{i+1})\subseteq A$ (respectively, $B$).

###### Proof.

It is enough to prove the claim for the case in which $v_{i},v_{i+1}\in A$ (as
the proof for the respective case is similar). If possible, assume that there
exists a vertex $b\in N_{H}(v_{i})\cap N_{H}(v_{i+1})$ such that $b\in B$.
This implies that $v_{i}b,v_{i+1}b\in E(G)$ (since $v_{i},v_{i+1}\in A$ and by
Observation 6). But we then have $v_{i}v_{i+1}\in E(G^{2})$, a contradiction.
Therefore, we can conclude that $N_{H}(v_{i})\cap N_{H}(v_{i+1})\subseteq A$.
Hence, the claim. ∎

Without loss of generality, by Claim 6, we can assume that $v_{i},v_{i+1}\in
A$, for some $i\in\\{0,1,\ldots,k\\}$. Then by Claim 6, we have
$V(H)\setminus\\{v_{i-1},v_{i+2}\\}=(N_{H}(v_{i})\cap
N_{H}(v_{i+1}))\cup\\{v_{i},v_{i+1}\\}\subseteq A$. Now, we will show that
even the remaining vertices $v_{i-1}$ and $v_{i+2}$ are also in $A$. Since
$k\geq 6$, we can find distinct vertices $v_{i+3},v_{i+4},v_{i+5}\in
V(H)\setminus\\{v_{i},v_{i+1},v_{i-1},v_{i+2}\\}$. Since
$V(H)\setminus\\{v_{i-1},v_{i+2}\\}\subseteq A$, we then have
$v_{i+3},v_{i+4},v_{i+5}\in A$. Note that $v_{i-1}\in N_{H}(v_{i+3})\cap
N_{H}(v_{i+4})$ and $v_{i+3},v_{i+4}\in A$. Similarly, $v_{i+2}\in
N_{H}(v_{i+4})\cap N_{H}(v_{i+5})$ and $v_{i+4},v_{i+5}\in A$. Therefore,
again by Claim 6, we have $v_{i-1},v_{i+2}\in A$. This together with the fact
that $V(H)\setminus\\{v_{i-1},v_{i+2}\\}\subseteq A$ implies that
$V(H)\subseteq A$. Recall that $H$ is an anti-hole of size larger than five.
This implies that $G^{2}[A]$ contains an odd anti-hole of size larger than
five as an induced subgraph. As this is a contradiction, we can conclude that
$G^{2}$ does not contain odd anti-holes of length larger than five. Hence, the
theorem. ∎

Let $G=(A,B,E)$ be a chordal bipartite graph. By a result in [21], both the
subgraphs, $G^{2}[A]$ and $G^{2}[B]$ (which they refer to as _half squares_ in
[21]) are chordal and therefore, perfect. Since perfect graphs are (odd
antihole)-free, we then have the following corollary due to Theorem 5.

######  Corollary 1.

Squares of chordal bipartite graphs do not contain odd anti-holes of size
larger than five.

In the remarks below, we note that the properties, namely, being _(even anti-
hole)-free or (hole)-free_ are not partite testable properties for the squares
of bipartite graphs in general.

Remark 1. (Even anti-hole)-free property is not partite testable in general:
Let $G=(A,B,E)$ be a bipartite graph with partite independent sets $A$ and
$B$. Even if both the induced subgraphs $G^{2}[A]$ and $G^{2}[B]$ do not
contain even anti-holes of size larger than four, $G^{2}$ may still contain
even anti-holes of any size larger than four. See Figure 3 for an illustration
(the edges of an even anti-hole in $G^{2}$ are shown in red). To be precise,
here, the induced subgraphs $G^{2}[A]$ and $G^{2}[B]$ do not contain any anti-
holes (as both the subgraphs induce cliques in $G^{2}$). But in $G^{2}$, the
set of vertices $\\{a_{2},b_{2},a_{3},b_{3},a_{4},b_{4}\\}$ induces an even
anti-hole of size six.

$a_{1}$$a_{2}$$a_{3}$$a_{4}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$ |  $a_{1}$$a_{2}$$a_{3}$$a_{4}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$
---|---
$G$ |  $G^{2}$
Figure 3: An illustration to show that _(even-hole)-free_ is not a partite
testable property

Remark 2. (Even hole)-free or (odd hole)-free properties are not partite
testable in general: Let $G=(A,B,E)$ be a convex bipartite graph with partite
independent sets $A$ and $B$. Even if both the subgraphs $G^{2}[A]$ and
$G^{2}[B]$ do not contain holes of length greater than three, $G^{2}$ may
contain holes of any length greater than three (see Figure 1 for an example).

Note that the structure of the graph $G^{2}$ given in Figure 1 is particularly
interesting. Later, we will see in Theorem 6 that any induced cycle of length
at least four that is present in the square of a convex bipartite graph
follows the same structure as the one in Figure 1; see the details in Theorem
6 for a precise statement.

Given a convex bipartite graph $G=(A,B,E)$, recall the definitions of
orderings $<_{A}$ and $<_{B}$ for the vertices in $A$ and $B$, respectively.
In the rest of the section, for $b_{i},b_{j}\in B$ with $b_{i}<_{B}b_{j}$, we
denote by $[b_{i},b_{j}]$, the set $\\{b\in B:b_{i}\leq_{B}b\leq_{B}b_{j}\\}$.
Further, we denote by $(b_{i},b_{j})$ the set
$[b_{i},b_{j}]\setminus\\{b_{i},b_{j}\\}$. Let $G=(A,B,E)$ be a bipartite
graph. For $k\geq 2$, we call an induced path $P=(a_{1},a_{2},\ldots,a_{k})$
in $G^{2}$ an _$(A,b,b^{\prime})$ -path_, if $V(P)\subseteq A$ and there exist
distinct vertices $b,b^{\prime}\in B$ such that $b\in
N_{G}(a_{1})\setminus\Big{(}\bigcup\limits_{j=2}^{k}N_{G}(a_{j})\Big{)}$ and
$b^{\prime}\in
N_{G}(a_{k})\setminus\Big{(}\bigcup\limits_{j=1}^{k-1}N_{G}(a_{j})\Big{)}$.
Note that if $P$ is an $(A,b,b^{\prime})$-path, then
$V(P)\cup\\{b,b^{\prime}\\}$ may induce either a path or cycle in $G^{2}$.
First, we note some properties of _$(A,b,b^{\prime})$ -paths_ that are present
in the square of a convex bipartite graph.

######  Observation 13.

Let $G=(A,B,E)$ be a convex bipartite graph with the orderings $<_{A}$ and
$<_{B}$. For $k\geq 2$, let $P=(a_{1},a_{2},\ldots,a_{k})$ be an
$(A,b,b^{\prime})$-path in $G^{2}$ with $a_{1}<_{A}a_{k}$. Then
$b<_{B}b^{\prime}$ and $a_{1}=\min_{<_{A}}\\{a_{j}\in V(P)\\}$.

###### Proof.

It is easy to see that $b<_{B}b^{\prime}$, as otherwise, by Observation 7
(with $a=a_{1}$ and $a^{\prime}=a_{k}$) we have $b\in N_{G}(a_{k})$, and this
contradicts the definition of $(A,b,b^{\prime})$-path. Now to prove the latter
part, let $a_{i}=\min_{<_{A}}\\{a_{j}\in V(P)\\}$. Note that
$a_{1}<_{A}a_{k}$. Suppose that $a_{i}=a_{j}$, for some
$j\in\\{2,3,\ldots,k-1\\}$. Then the vertices $a_{j-1},a_{j+1}$ exist, and are
such that $a_{j}<_{A}a_{j-1},a_{j+1}$, and $a_{j-1},a_{j+1}\in
N_{P}(a_{j})\subseteq N_{G^{2}[A]}(a_{j})$. By Observation 8, we then have
$a_{j-1}a_{j+1}\in E(G^{2}[A])$. This contradicts the fact that $P$ is an
induced path. Therefore, we can conclude that $a_{i}=a_{1}$.

∎

######  Lemma 5.

Let $G=(A,B,E)$ be a convex bipartite graph with the orderings $<_{A}$ and
$<_{B}$. For $k\geq 2$, let $P=(a_{1},a_{2},\ldots,a_{k})$ be an
$(A,b,b^{\prime})$-path in $G^{2}$ with $a_{1}<_{A}a_{k}$. Then the following
hold:

  1. ($a$)

If $k=2$, we have $N_{G}(a_{1})\cap N_{G}(a_{k})\subseteq(b,b^{\prime})$. If
$k>2$, for each $j\in\\{2,3,\ldots,k-1\\}$, we have
$N_{G}(a_{j})\subseteq(b,b^{\prime})$.

  2. ($b$)

For each $\tilde{b}\in[b,b^{\prime}]$, there exists $j\in\\{1,2,\ldots,k\\}$
such that $\tilde{b}\in N_{G}(a_{j})$.

###### Proof.

($a$) Note that $b<_{B}b^{\prime}$ by Observation 13. If $k=2$, then as
$a_{1}a_{k}\in E(G^{2})$, $N_{G}(a_{1})\cap N_{G}(a_{k})\neq\emptyset$.
Further, by the consecutive property of the ordering $<_{B}$, and the
definitions of $b$ and $b^{\prime}$, we have $N_{G}(a_{1})\cap
N_{G}(a_{k})\subseteq(b,b^{\prime})$. Suppose that $k>2$. If possible, let
$a_{j}$, where $j\in\\{2,3,\ldots,k-1\\}$ be the first vertex along the path
$P$ for which ($a$) is not true. i.e. let $j=\min\\{2,3,\ldots,k-1\\}$ be such
that $N_{G}(a_{j})\nsubseteq(b,b^{\prime})$.

Recall that $b,b^{\prime}\notin N_{G}(a_{j})$. Thus by the definition of
$<_{B}$, if $a_{j}$ has a neighbor $b_{l}\in(b,b^{\prime})$ then we have
$N_{G}(a_{j})\subseteq(b,b^{\prime})$, a contradiction, and we are done.
Therefore we can assume that $N_{G}(a_{j})\cap[b,b^{\prime}]=\emptyset$. But
then it should be the case that $j=2$. (As otherwise, $j-1\geq 2$ and by the
choice of $j$ we have $N_{G}(a_{j-1})\subseteq(b,b^{\prime})$. This implies
that $N_{G}(a_{j-1})\cap N_{G}(a_{j})=\emptyset$, and contradicts the fact
that $a_{j-1}a_{j}\in E(G^{2})$.) Now since $b^{\prime}\notin N_{G}(a_{1})$
and $a_{1}a_{2}\in E(G^{2})$, $N_{G}(a_{2})\nsubseteq[b,b^{\prime}]$ implies
that $N_{G}(a_{2})\subseteq[b_{1},b-1]$, where $b_{1}=\min_{<_{B}}\\{b\in
B\\}$. Since $a_{2}a_{3}\in E(G^{2})$ and $b\notin N_{G}(a_{3})$, by the
consecutive property of $<_{B}$ we then have
$N_{G}(a_{3})\subseteq[b_{1},b-1]$. For each $l\geq 3$, by repeating the same
arguments along the edges $a_{l}a_{l+1}$ in $G^{2}$, we finally get
$N_{G}(a_{k})\subseteq[b_{1},b-1]$. As $b<_{B}b^{\prime}$, the consecutive
property of $<_{B}$ implies that $b^{\prime}\notin N_{G}(a_{k})$, a
contradiction. Therefore, ($a$) is true.

($b$) Suppose not. Let $x\in[b,b^{\prime}]$ be such that for any
$j\in\\{1,2,\ldots,k\\}$, $x\notin N_{G}(a_{j})$. Consider the vertex $a_{2}$.
By ($a$), $N_{G}(a_{2})\subseteq(b,b^{\prime})$. Since $a_{1}a_{2}\in
E(G^{2})$ there exists a vertex $y\in B$ such that $a_{1}y,a_{2}y\in E(G)$. As
$b\in N_{G}(a_{1})$, $y\in N_{G}(a_{1})\cap N_{G}(a_{2})$ and $x\notin
N_{G}(a_{1})\cup N_{G}(a_{2})$, by the consecutive property of the ordering
$<_{B}$, we have $N_{G}(a_{2})\subseteq(b,x)$. Now for each $l\geq 2$, by
repeating the same arguments along the edges $a_{l}a_{l+1}$ in $G^{2}$, we
finally get $N_{G}(a_{k})\subseteq(b,x)$. Since $x<_{B}b^{\prime}$, the
consecutive property of $<_{B}$ implies that $b^{\prime}\notin N_{G}(a_{k})$.
This is a contradiction and hence proves ($b$). ∎

We now have the following corollary of Lemma 5.

######  Corollary 2.

Let $G=(A,B,E)$ be a convex bipartite graph. Let $C$ be an induced cycle in
$G^{2}$ and let $P=(a_{1},a_{2},\ldots,a_{k})$ (where $k\geq 2$), be a sub-
path (recall the definition from Section 1.2) of $C$ which is also an
$(A,b,b^{\prime})$-path. If $b,b^{\prime}\in B\cap V(C)$ then
$(b,b^{\prime})\cap V(C)=\emptyset$.

###### Proof.

Suppose not. Let $x\in(b,b^{\prime})\cap V(C)$. Then by Lemma 5($b$), there
exists a vertex $a_{j}\in V(P)$ such that $xa_{j}\in E(G)\subseteq E(G^{2})$.
This contradicts the fact that $C$ is an induced cycle. ∎

Let $G$ be a convex bipartite graph. Since the class of convex bipartite
graphs forms a subclass of chordal bipartite graphs, by Corollary 1, $G^{2}$
does not contain odd antiholes of size larger than five. Therefore, by the
Strong Perfect Graph Theorem, the sole reason for the non-perfectness of the
squares of convex bipartite graphs is due to the presence of odd holes (note
that an odd antihole of size five is isomorphic to its complement $C_{5}$, the
odd hole of size five). In the following observations and lemmas, we study the
structure of holes that are present in the squares of convex bipartite graphs.

######  Observation 14.

Let $G=(A,B,E)$ be a convex bipartite graph with the orderings $<_{A}$ and
$<_{B}$, and let $C$ be an induced cycle in $G^{2}$ of length $k\geq 4$. Then
$V(C)\cap A\neq\emptyset$ and $V(C)\cap B\neq\emptyset$. Moreover, if the
vertices in $C$ are labeled such that $C=(v_{1},v_{2},\ldots,v_{k})$ with
$v_{1}=\min_{<_{A}}\\{v_{l}:v_{l}\in V(C)\cap A\\}$, then exactly one of the
vertices in the set $\\{v_{2},v_{k}\\}$ belongs to $A$ and the other is in
$B$.

###### Proof.

By Observation 5 and Lemma 3, both the subgraphs $G^{2}[A]$ and $G^{2}[B]$ are
interval graphs and therefore, chordal. Since $C$ is an induced cycle of
length at least 4 in $G^{2}$, we then have $V(C)\nsubseteq A$ and
$V(C)\nsubseteq B$. This implies that $V(C)\cap A\neq\emptyset$ and $V(C)\cap
B\neq\emptyset$. Let $v_{1}=\min_{<_{A}}\\{v_{l}:v_{l}\in V(C)\cap A\\}$. Now
consider the vertices $v_{2}$ and $v_{k}$ in $C$. If
$\\{v_{2},v_{k}\\}\subseteq A$ then $v_{1}<_{A}v_{2},v_{k}$ and
$\\{v_{2},v_{k}\\}\subseteq N_{C}(v_{1})\subseteq N_{G^{2}}(v_{1})$. This
implies by Observation 8 that $v_{2}v_{k}\in E(G^{2})$, a contradiction to the
fact that $C$ is an induced cycle. Now if $\\{v_{2},v_{k}\\}\subseteq B$ then
$\\{v_{2},v_{k}\\}\subseteq N_{C}(v_{1})\subseteq N_{G}(v_{1})$ (as $v_{1}\in
A$ and $v_{2},v_{k}\in B$, by Observation 6). This implies that $v_{2}v_{k}\in
E(G^{2})$, again a contradiction. As we have a contradiction in both cases, we
can conclude that exactly one of the vertices in $\\{v_{2},v_{k}\\}$ belongs
to $A$ and the other is in $B$.

∎

######  Lemma 6.

Let $G=(A,B,E)$ be a convex bipartite graph with the orderings $<_{A}$ and
$<_{B}$ and let $C$ be an induced cycle in $G^{2}$ of length $k\geq 4$. Then
the vertices in $C$ can be labeled as $C=(v_{1},v_{2},\ldots,v_{k})$ with
$v_{1}=\min_{<_{A}}\\{v_{l}:v_{l}\in V(C)\cap A\\}$ such that the sub-path
$(v_{1},v_{2},\ldots,v_{k-2})$ is an $(A,v_{k},v_{k-1})$-path.

###### Proof.

By Observation 14, if $v_{1}=\min_{<_{A}}\\{v_{l}:v_{l}\in V(C)\cap A\\}$ then
exactly one of the vertices in $\\{v_{2},v_{k}\\}$ belongs to $A$ and the
other is in $B$. Without loss of generality, we can assume that $v_{2}\in A$
and $v_{k}\in B$ (as in the other case, we can first enumerate the cycle by
starting at $v_{1}$ itself but in the reverse direction and use the same
arguments below). Now, while traversing $C$ starting from $v_{1}\in A$ along
the increasing order of their indices in $C$, namely, $v_{1},v_{2},\ldots,$ in
$A$, we can find a vertex, say $v_{j}\in V(C)\cap A$ such that
$\\{v_{1},v_{2},\ldots,v_{j}\\}\subseteq A$, but $v_{j+1}\in B$. If
$v_{j+1}=v_{k}$ then $v_{j}v_{k},v_{1}v_{k}\in E(C)\subseteq E(G)$ (since
$v_{j},v_{1}\in A$ and $v_{k}\in B$, by Observation 6). This implies that
$v_{1}v_{j}\in E(G^{2})$, a contradiction to the fact that $C$ is an induced
cycle of length at least four in $G^{2}$. Thus we have $v_{j+1}\neq v_{k}$,
and therefore $j\leq k-2$. Moreover, $v_{k}\in
N_{G}(v_{1})\setminus\Big{(}\bigcup\limits_{p=2}^{j}N_{G}(v_{p})\Big{)}$ and
$v_{j+1}\in
N_{G}(v_{j})\setminus\Big{(}\bigcup\limits_{p=1}^{j-1}N_{G}(v_{p})\Big{)}$.
Therefore, $P_{0}=(v_{1},v_{2},\ldots,v_{j})$ is an $(A,v_{k},v_{j+1})$-path
and by Observation 13, we have $v_{k}<_{B}v_{j+1}$. Observe that if
$v_{k}v_{j+1}\in E(G^{2})$ then $v_{j+1}=v_{k-1}$, $v_{j}=v_{k-2}$, and we are
done. We intend to show that $v_{k}v_{j+1}\in E(G^{2})$ is always true.

For the sake of contradiction, suppose that $v_{k}v_{j+1}\notin E(G^{2})$.
Then consider the sub-path of $C$ namely,
$P_{1}:(v_{k},v_{k-1},\ldots,v_{j+2},v_{j+1})$ (starting from the vertex
$v_{k}$ in $C$ traverse along the reverse direction all the way to $v_{j+1}$).
Note that $|V(P_{1})|\geq 3$ (since $v_{k}v_{j+1}\notin E(G^{2})$) and
$V(C)=V(P_{0})\uplus V(P_{1})$. Let $b_{1}$ be the minimum indexed vertex in
$B$ with respect to the ordering $<_{B}$. We then claim that
$V(P_{1})\setminus\\{v_{j+1}\\}\subseteq[b_{1},v_{k}]$. Suppose not. Let
$v_{p}$ be the first vertex with respect to the order of their appearance in
$P_{1}$ such that $v_{p}\notin[b_{1},v_{k}]$. We then have the following
cases.

Case-1 $v_{p}\in A$: Recall that $v_{1}\in A$, $v_{k}\in B$. Therefore,
$v_{p}\in A$ implies that $v_{p}\neq v_{k-1}$. As otherwise,
$v_{p}v_{k},v_{1}v_{k}\in E(C)\subseteq E(G)$ (by Observation 6). This implies
that $v_{p}v_{1}\in E(G^{2})$, a contradiction (since $2<j+1<p<k$). Recall
that $v_{1}<_{A}v_{p}$. By the choice of $v_{p}$ and the fact that $v_{p}\neq
v_{k-1}$, we also have $b_{1}\leq_{B}v_{p-1}<_{B}v_{k}$. Then as
$v_{1}v_{k},v_{p}v_{p-1}\in E(C)\subseteq E(G)$ (as $v_{1},v_{p}\in A$ and
$v_{k},v_{p-1}\in B$, by Observation 6), by Observation 7 (with $a=v_{1}$,
$a^{\prime}=v_{p}$, $b=v_{k}$, and $b^{\prime}=v_{p-1}$), we get
$v_{p}v_{k}\in E(G^{2})$, a contradiction (since $v_{p}\neq v_{k-1},v_{1}$).

Case-2 $v_{p}\in B:$ Here we have two subcases.

Case-2.1 $v_{p}\in(v_{k},v_{j+1})$: Since $P_{0}$ is an
$(A,v_{k},v_{j+1})$-path and $v_{p}\in V(C)$, by Corollary 2 applied to
$P_{0}$, we have $v_{p}\notin(v_{k},v_{j+1})$, a contradiction.

Case-2.2 $v_{j+1}<_{B}v_{p}$: By the choice of $v_{p}$, we then have
$b_{1}\leq_{B}v_{p-1}\leq_{B}v_{k}<_{B}v_{j+1}<_{B}v_{p}$. Now since $<_{B}$
is a proper interval ordering (by Lemma 3), $v_{p-1}v_{p}\in E(G^{2})$ implies
that $v_{p-1}v_{j+1},v_{j+1}v_{p}\in E(G^{2})$, and therefore,
$\\{v_{p-1},v_{p},v_{j+1}\\}$ forms a triangle in $G^{2}$. This contradicts
the fact that $C$ is an induced cycle of length at least 4 in $G^{2}$.

Since we have a contradiction to the existence of $v_{p}$ in all the possible
cases, we can conclude that
$V(P_{1})\setminus\\{v_{j+1}\\}\subseteq[b_{1},v_{k}]$. Now consider the
vertex $v_{j+2}\in V(P_{1})\setminus\\{v_{k},v_{j+1}\\}$ (such a vertex
$v_{j+2}$ exists since $|V(P_{1})|\geq 3$). It follows that
$v_{j+2}\in[b_{1},v_{k}]$. This implies that
$b_{1}<_{B}v_{j+2}<_{B}v_{k}<_{B}v_{j+1}$. Further, as $<_{B}$ is a proper
interval ordering (by Lemma 3), the fact that $v_{j+2}v_{j+1}\in E(G^{2})$
implies that $v_{k}v_{j+1}\in E(G^{2})$, and therefore, a contradiction. This
completes the proof of the lemma. ∎

We are now ready to prove the following theorem on the structure of holes that
is present in the squares of convex bipartite graphs.

######  Theorem 6.

Let $G=(A,B,E)$ be a convex bipartite graph with the orderings $<_{A}$ and
$<_{B}$. Let $C$ be an induced cycle in $G^{2}$ of length at least 4. Then the
following hold:

  1. ($a$)

The vertices in $C$ can be labelled as $(v_{1},v_{2}\ldots,v_{k})$, $k\geq 4$
such that the sub-path $P=(v_{1},v_{2},\ldots,v_{k-2})$ is an
$(A,v_{k},v_{k-1})$-path.

  2. ($b$)

There exists a set of vertices
$\\{b_{1},b_{2},\ldots,b_{k-3}\\}\subseteq(v_{k},v_{k-1})$ such that for each
$i\in\\{1,2,\ldots,\\\ k-3\\}$, we have $N_{G}(b_{i})\cap
V(P)=\\{v_{i},v_{i+1}\\}$. Further,
$v_{k}<_{B}b_{1}<_{B}\cdots<_{B}b_{k-3}<_{B}v_{k-1}$ and
$v_{1}<_{A}v_{2}<_{A}\cdots<_{A}v_{k-2}$.

  3. ($c$)

There exists a vertex $a\in A$ such that
$\\{v_{k},b_{1},b_{2},\ldots,b_{k-3},v_{k-1}\\}\subseteq N_{G}(a)$.

###### Proof.

($a$) Let $v_{1}=\min_{<_{A}}\\{v_{i}:v_{i}\in V(C)\cap A\\}$. Then Part ($a$)
is essentially same as Lemma 6.

($b$) Let $b_{0}=v_{k}$ and $i\in\\{1,2,\ldots,k-3\\}$. Since $P$ is an
induced path in $G^{2}[A]$, $N_{G}(v_{i})\cap N_{G}(v_{i+1})\neq\emptyset$ for
each $i$. Let $b_{i}\in N_{G}(v_{i})\cap N_{G}(v_{i+1})$. Note that
$b_{i}\notin N_{G}(v_{j})$ for each $j\neq i,i+1$ (as otherwise
$\\{v_{i},v_{i+1},v_{j}\\}$ forms a triangle in $G^{2}$, a contradiction).

We now recursively do the following procedure for $i\in\\{1,2,\ldots,k-3\\}$:
Consider the sub-path $P_{i}=(v_{i},v_{i+1},\ldots,v_{k-2})$. Clearly, $P_{i}$
is an $(A,b_{i-1},v_{k-1})$-path. And by Lemma 5($a$),
$b_{i}\in(N_{G}(v_{i})\cap N_{G}(v_{i+1}))\subseteq(b_{i-1},v_{k-1})$.
Therefore, we have the set of vertices $\\{b_{1},b_{2},\ldots,b_{k-3}\\}$ in
$B$ having the property that
$v_{k}<_{B}b_{1}<_{B}\cdots<_{B}b_{k-3}<_{B}v_{k-1}$ and $N_{G}(b_{i})\cap
V(P)=\\{v_{i},v_{i+1}\\}$. Since for each $i\in\\{1,2,\ldots,k-3\\}$,
$v_{i}\in N_{G}(b_{i})\setminus N_{G}(b_{i+1})$, this implies by the
definition of $<_{A}$ that $v_{1}<_{A}v_{2}<_{A}\cdots<_{A}v_{k-2}$. This
proves ($b$).

($c$) Since $v_{k}v_{k-1}\in E(C)\subseteq E(G^{2}[B])$ (as $v_{k},v_{k-1}\in
B$), there exists a vertex $a\in A$ such that $v_{k},v_{k-1}\in N_{G}(a)$.
Recall that $v_{k}<_{B}b_{1}<_{B}\cdots<_{B}b_{k-3}<_{B}v_{k-1}$ (by ($b$)).
This implies by the consecutive property of $<_{B}$ that
$\\{v_{k},b_{1},b_{2},\ldots,b_{k-3},v_{k-1}\\}\subseteq N_{G}(a)$, and proves
($c$). ∎

We then have the following corollaries of Theorem 6.

######  Corollary 3.

Let $G=(A,B,E)$ be a convex bipartite graph. Let
$\\{\overline{S},S\\}=\\{A,B\\}$, where $S$ is the partite set of $G$ whose
vertices have an ordering with a consecutive property and
$\overline{S}=V(G)\setminus S$. If $C$ is an induced cycle of length $k\geq 4$
then $|V(C)\cap S|=2$ and $|V(C)\cap\overline{S}|=k-2$.

###### Proof.

The vertices in the partite set $S$ of $G$ always admit an ordering as in the
definition of the ordering $<_{B}$, and the vertices in $\overline{S}$ always
admit an ordering as in the definition of the ordering $<_{A}$ (see the
definitions of $<_{A}$ and $<_{B}$ defined at the beginning of Section 3). The
proof of the corollary now easily follows from Theorem 6($a$) and the
definition of an $(A,b,b^{\prime})$ path. ∎

######  Corollary 4.

Let $G$ be a convex bipartite graph. If $G^{2}$ contains an induced cycle of
length $k\geq 4$, then $G^{2}$ contains induced cycles of length $k^{\prime}$
for each $4\leq k^{\prime}\leq k$.

###### Proof.

Let $C$ be an induced cycle in $G^{2}$ of length $k$, where $k\geq 4$. Then by
Theorem 6($a$), the vertices in $C$ can be labelled as
$C=(v_{1},\ldots,v_{k})$, where $P=(v_{1},v_{2},\ldots,v_{k-2})$ is an
$(A,v_{k},v_{k-1})$-path. Further by Theorem 6($b$), there exists a set of
vertices, say $B^{\prime}=\\{b_{1},b_{2},\ldots,b_{k-3}\\}\subseteq B$ such
that for each $j\in\\{1,2,\ldots,k-3\\}$, $N_{G}(b_{j})\cap
V(P)=\\{v_{j},v_{j+1}\\}$. Also, by Theorem 6($c$), the set
$B^{\prime}\cup\\{v_{k},v_{k-1}\\}$ forms a clique in $G^{2}$. Let
$b_{k-2}=v_{k-1}$. For each $i\in\\{2,\ldots,k-2\\}$, define
$C_{i}=(v_{1},v_{2},\ldots,v_{i},b_{i},v_{k})$. As $C$ is an induced cycle and
$N_{C_{i}}(b_{i})=\\{v_{i},v_{k}\\}$, this implies that $C_{i}$ is an induced
cycle in $G^{2}$ of length $i+2$. Hence the corollary. ∎

Recall that a graph $H$ is said to be perfect if and only if $H$ is both (odd
hole)-free and (odd antihole)-free; an odd antihole of length five is
isomorphic to its complement $C_{5}$, the odd-hole of length five. A graph $H$
is chordal if it does not contain induced cycles of length at least four. For
a convex bipartite graph $G=(A,B,E)$, we have that both the subgraphs
$G^{2}[A]$ and $G^{2}[B]$ are interval graphs and, therefore, chordal and
hence perfect. Moreover, since the class of convex bipartite graphs forms a
subclass of chordal bipartite graphs, by Corollary 1, we have that $G^{2}$
does not contain odd-antiholes of length greater than five. Now, the following
theorem is an easy consequence of Corollary 4.

######  Theorem 7.

Let $G$ be a convex bipartite graph. Then, we have the following.

  1. ($a$)

If $G^{2}$ is $C_{5}$-free, then $G^{2}$ is perfect. i.e. perfectness is a
partite testable property for $C_{5}$-free squares of convex bipartite graphs.

  2. ($b$)

If $G^{2}$ is $C_{4}$-free, then $G^{2}$ is chordal. i.e. chordality is a
partite testable property for $C_{4}$-free squares of convex bipartite graphs.

Now, let us focus on a well-known subclass of convex bipartite graphs, namely
biconvex bipartite graphs.

######  Definition 6 (Biconvex bipartite graph).

A bipartite graph $G=(A,B,E)$ is said to be biconvex bipartite if the vertices
in $A$ and $B$, respectively, have orderings, say $<_{A}^{\prime}$ and $<_{B}$
such that, for each vertex $a\in A$ (respectively, $b\in B$), the vertices in
the neighborhood of $a$ (respectively, $b$) in $G$ appear consecutively with
respect to the ordering $<_{B}$ (respectively, $<_{A}^{\prime}$).

$v_{1}$$a$$v_{2}$$v_{4}$$b$$v_{3}$ |  $v_{1}$$a$$v_{2}$$v_{4}$$b$$v_{3}$
---|---
$G$ |  $G^{2}$
Figure 4: A biconvex bipartite graph $G$ such that $G^{2}$ is not chordal

We first note the following remark.

Remark 3. Chordality is not a partite testable property for the squares of
biconvex bipartite graphs: For a biconvex bipartite graph $G=(A,B,E)$, since
both the partite sets have the consecutive ordering property, it is not
difficult to infer from Lemma 3 that both the subgraphs $G^{2}[A]$ and
$G^{2}[B]$ are proper interval graphs. But the squares of biconvex bipartite
graphs need not be chordal. See Figure 4 for an example of a biconvex
bipartite graph $G$ for which $G^{2}$ is not chordal (the edges shown in red
form an induced $C_{4}$).

However, we have the following corollary of Theorem 6, which implies that
_perfectness is a partite testable property for the squares of biconvex
bipartite graphs_.

######  Theorem 8.

The squares of biconvex bipartite graphs are $C_{5}$-free and hence perfect.

###### Proof.

Suppose not. Let $G=(A,B,E)$ be a biconvex bipartite graph. Then, the vertices
in both the partite sets $A$ and $B$ admit consecutive orderings (see
Definition 6). Suppose that $C$ is an induced cycle in $G^{2}$ of length five.
Take $S=A$ and $\overline{S}=B$. Then, as the conditions in Corollary 3 are
satisfied, we get that $|V(C)\cap A|=2$. Now take $S=B$ and $\overline{S}=A$,
then also the conditions in the same corollary are satisfied, and we have
$|V(C)\cap B|=2$. Since $V(C)\subseteq A\cup B$, this implies that $|V(C)|\leq
4<5$, a contradiction. Therefore, we can conclude that the squares of biconvex
bipartite graphs are $C_{5}$-free and hence perfect by Theorem 7($a$). ∎

Remark 4. Let $\mathcal{C}$ denote the class of $C_{5}$-free squares of convex
bipartite graphs, $\mathcal{C}_{1}$ denote the class of $C_{4}$-free squares
of convex bipartite graphs, and $\mathcal{C}_{2}$ denote the class of squares
of biconvex bipartite graphs. By Corollary 4 and Theorem 8, respectively, we
have $\mathcal{C}_{1},\mathcal{C}_{2}\subseteq\mathcal{C}$. By a previous
observation (recall Figure 4), we have noted that the squares of biconvex
bipartite graphs may contain $C_{4}$ as an induced subgraph. This implies that
$\mathcal{C}_{2}\nsubseteq\mathcal{C}_{1}$. In fact, we can observe that
$\mathcal{C}_{1}\nsubseteq\mathcal{C}_{2}$ as well. i.e. there exists convex
bipartite graphs $G$ such that $G^{2}$ is $C_{4}$-free but $G$ is not a
biconvex bipartite graph. See Figure 5 for an example. It is not difficult to
see that $G$ is a convex bipartite graph but not biconvex (since there are 3
vertices $b_{i}$, $i\in\\{1,2,3\\}$ in $B$ such that for each vertex $b_{i}$,
the vertex $a_{i}\in A$ is an exclusive neighbor of $b_{i}$, whereas all the
three vertices have the vertex $a$ as their common neighbor in $G$). On the
other hand, $G^{2}$ is clearly $C_{4}$-free, implying that
$\mathcal{C}_{1}\nsubseteq\mathcal{C}_{2}$.

$a$$a_{1}$$a_{2}$$a_{3}$$b_{1}$$b_{2}$$b_{3}$ |  $a$$a_{1}$$a_{2}$$a_{3}$$b_{1}$$b_{2}$$b_{3}$
---|---
$G$ |  $G^{2}$
Figure 5: A convex bipartite graph $G$ such that $G$ is not biconvex, but
$G^{2}$ is $C_{4}$-free

## References

  * [1] G. Agnarsson and M. M. Halldórsson.  Coloring powers of planar graphs.  SIAM Journal on Discrete Mathematics, 16(4):651–662, 2003.
  * [2] N. Alon and B. Mohar.  The chromatic number of graph powers.  Combinatorics, Probability and Computing, 11:1 – 10, 2002.
  * [3] V. Boncompagni, I. Penev, and K. V. sković.  Clique cutsets beyond chordal graphs.  Electronic Notes in Discrete Mathematics, 62:81–86, 2017.
  * [4] K. S. Booth and G. S. Lueker.  Testing for the consecutive ones property, interval graphs, and graph planarity using $pq$-tree algorithms.  Journal of Computer and System Sciences, 13(3):335–379, 1976.
  * [5] T. Calamoneri, S. Caminiti, R. Petreschi, and S. Olariu.  On the $l(h,k)$-labeling of co-comparability graphs and circular-arc graphs.  Networks, 53(1):27–34, 2009.
  * [6] I. Choi, D. W. Cranston, and T. Pierron.  Degeneracy and colorings of squares of planar graphs without 4-cycles.  Combinatorica, 40(5):625–653, 2020.
  * [7] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas.  The strong perfect graph theorem.  Annals of mathematics, pages 51–229, 2006.
  * [8] D. W. Cranston.  Coloring, list coloring, and painting squares of graphs (and other related problems).  arXiv preprint arXiv:2210.05915, 2022.
  * [9] W. Dong and B. Xu.  2-distance coloring of planar graphs without 4-cycles and 5-cycles.  SIAM Journal on Discrete Mathematics, 33(3):1297–1312, 2019.
  * [10] Z. Dvořák, P. Nejedlỳ, and R. Škrekovski.  Coloring squares of planar graphs with girth six.  European Journal of Combinatorics, 29(4):838–849, 2008.
  * [11] P. Fraigniaud, M. M. Halldórsson, and A. Nolin.  Distributed testing of distance-$k$ colorings.  In Structural Information and Communication Complexity: 27th International Colloquium (SIROCCO), page 275–290, 2020.
  * [12] M. C. Golumbic.  Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57).  North-Holland Publishing Co., 2004.
  * [13] M. M. Halldórsson, F. Kuhn, and Y. Maus.  Distance-2 coloring in the congest model.  In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), page 233–242, 2020.
  * [14] I. A. Karapetian.  On coloring of arc graphs.  Dokladi of the Academy of Science of the Armenian SSR, 70(5):306–311, 1980.
  * [15] T. Karthick and F. Maffray.  Coloring (gem, co-gem)-free graphs.  Journal of Graph Theory, 89(3):288–303, 2018.
  * [16] T. Karthick and F. Maffray.  Square-free graphs with no six-vertex induced path.  SIAM Journal on Discrete Mathematics, 33(2):874–909, 2019.
  * [17] A. B. Kempe.  On the geographical problem of the four colours.  American journal of mathematics, 2(3):193–200, 1879.
  * [18] B. Klemz and G. Rote.  Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs.  Algorithmica, 84(4):1064–1080, 2022.
  * [19] T. Kloks, H. Müller, and K. Vušković.  Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences.  Journal of Combinatorial Theory, Series B, 99(5):733–800, 2009\.
  * [20] F. Kramer and H. Kramer.  A survey on the distance-colouring of graphs.  Discrete Mathematics, 308(2):422–426, 2008.
  * [21] H.-O. Le and V. B. Le.  Hardness and structural results for half-squares of restricted tree convex bipartite graphs.  Algorithmica, 81:4258–4274, 2019.
  * [22] M. Molloy and M. R. Salavatipour.  A bound on the chromatic number of the square of a planar graph.  Journal of Combinatorial Theory, Series B, 94(2):189–213, 2005\.
  * [23] A. Scott and P. Seymour.  A survey of $\chi$-boundedness.  Journal of Graph Theory, 95(3):473–504, 2020.
  * [24] C. Thomassen.  The square of a planar cubic graph is 7-colorable.  Journal of Combinatorial Theory, Series B, 128:192–218, 2018.
  * [25] A. Tucker.  Coloring a family of circular arcs.  SIAM Journal on Applied mathematics, 29(3):493–502, 1975.
  * [26] M. Valencia-Pabon.  Revisiting tucker’s algorithm to color circular arc graphs.  SIAM Journal on Computing, 32(4):1067–1072, 2003.
  * [27] J. van den Heuvel and S. McGuinness.  Coloring the square of a planar graph.  Journal of Graph Theory, 42(2):110–124, 2003.
  * [28] J. Zhu, Y. Bu, and H. Zhu.  Wegner’s conjecture on 2-distance coloring for planar graphs.  Theoretical Computer Science, 926:71–74, 2022.