Weak Modular Product of Bipartite Graphs, Bicliques
and Isomorphism
Danial Dervovic∗

Simone Severini∗†

arXiv:1707.05179v1 [math.CO] 17 Jul 2017

July 18, 2017

Abstract
A 1978 theorem of Kozen states that two graphs on n vertices are isomorphic
if and only if there is a clique of size n in the weak modular product between
the two graphs. Restricting to bipartite graphs and considering complete bipartite
subgraphs (bicliques) therein, we study the combinatorics of the weak modular
product. We identify cases where isomorphism is tractable using this approach,
which we call Isomorphism via Biclique Enumeration (IvBE). We find that IvBE is
polynomial for bipartite 2K2 -free graphs and quasi-polynomial for families of bipartite graphs, where the largest induced matching and largest induced crown graph
grows slowly in n, that is, O(poly log n). Furthermore, as expected a straightforward corollary of Kozen’s theorem and Lovász’s sandwich theorem is if the weak
modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in n. However, we show that for balanced, bipartite graphs
this is only true in a few trivial cases. In doing so we define a new graph product on bipartite graphs, the very weak modular product. The results pertaining to
bicliques in bipartite graphs proved here may be of independent interest.

1

Introduction

Graph products have been extensively studied and are of vast theoretical and practical
interest, see, e.g., Hammack, Imrich and Klavžar [HIK11]. A common problem is to
determine how graph invariants such as the independence number and clique number
behave under the action of a particular graph product. For instance, a famous result
of Lovász [Lov79] states that for graphs G and H, ϑ(G  H) = ϑ(G)ϑ(H), where ϑ( · )
denotes the Lovász number and  is the strong graph product. There are three graph
products that have received most attention in the literature: the aforementioned strong
∗

Department of Computer Science, University College London, Gower Street, London WC1E 6BT,
United Kingdom; mailto: d.dervovic@cs.ucl.ac.uk.
†
Institute of Natural Sciences, Shanghai Jiao Tong University, No. 800 Dongchuan Road, Minhang
District, Shanghai 200240, China.

1

graph product, the direct (or tensor) product and the Cartesian product. These three
graph products are the most studied as they satisfy the following: they are associative
and projections onto the factors are weak homomorphisms. Loosely speaking, the second
property means that the adjacency structure of the product graph allows one to infer
the adjacency structure of the factor graphs.
One can consider graph products that do not satisfy the second property. Such a
product is the weak modular product, whose adjacency structure also includes information about non-adjacency in the factor graphs. Interestingly, as originally proved by
Kozen [Koz78], a clique of a certain size exists in the product graph if and only if the
factors are isomorphic. Since the decision version of finding the clique number of a general graph is NP-complete, this result has largely been ignored in the literature with
reference to graph isomorphism.
The graph isomorphism problem (GI) has been studied extensively for decades, but
its complexity status remains unknown. Clearly, GI ∈ NP as one can check easily if
a given candidate isomorphism preserves all adjacencies and non-adjacencies between
the two graphs at hand. However, it is unlikely that GI is NP-complete as this would
imply collapse of the polynomial hierarchy [GMW91]. The question of whether GI ∈
P remains open. There has been a considerable research effort to find a polynomialtime algorithm for GI, culminating recently in the recent quasi-polynomial algorithm
by Babai [Bab15]. However, there are many classes of graph for which GI admits a
polynomial-time algorithm, for instance graphs with a forbidden minor [Pon91, Gro10],
including planar graphs and graphs of bounded genus. In practice, the approach of
McKay and Piperno [MP14] works efficiently on almost all graphs and so efficiently
solving GI ‘in the wild’ is all but solved.
Many of the recent advances in GI, including Babai’s recent breakthrough [Bab15]
and the nauty/ traces programs of McKay and Piperno [MP14] use a group theoretic
approach. In this paper we consider a combinatorial approach, which was the primary
method for GI in the earlier days of its study, but also make use of contemporary ideas
from outside this tradition. The combinatorial construction we consider is the weak
modular product, mentioned earlier. This construction has been used in the pattern
recognition community under the label association graph to solve graph matching problems [PSZ99, CFSV04]. Indeed, Pelillo [Pel99] uses a heuristic inspired by theoretical
biology to find cliques in the weak modular product as an approach to inexact graph
matching, a problem that one can interpret as an approximation to isomorphism. He
provides computational evidence that this technique is tractable for this problem in
certain regimes.
Here we examine the combinatorics of the weak modular product of bipartite graphs.
Bipartite graphs are of particular interest, since deciding if two bipartite graphs are
isomorphic is GI-complete [UTN05]. We study cliques in the weak modular product
analytically, considering this as an approach for GI. We find that in the bipartite case,
bicliques play a similar role to cliques in the weak modular product. Recall that a
biclique is a fully connected bipartite subgraph. Finding bicliques in bipartite graphs
2

has garnered much interest in the bioinformatics community, since this can be applied
to tasks such as identifying common gene-set associations [CL07] and integrating diverse
functional genomics data [BJP+ 09]. In this work, we use results on finding bicliques in
bipartite graphs commonly used by bioinformaticians.
In particular, we propose an algorithm, IvBE (Algorithm 1) for isomorphism of bipartite graphs based on Kozen’s theorem and counting bicliques. We show that this
algorithm runs in polynomial time for bipartite 2K2 -free graphs (Proposition 12) and in
quasi-polynomial time for families of bipartite graphs where the largest induced matching
and the largest induced crown graph grow polylogarithmically in the number of vertices
(Proposition 11). Bipartite 2K2 -free graphs are also known under a different name, difference graphs [HPS90]. A graph is a difference graph if every vertex ui can be assigned
a real number ai ad there exists a positive real number T such that i. |ai | < T for all i
and ii. ui ∼ uj if and only if |ai − aj | ≥ T . For this class of graphs, GI is already known
to be polynomial, as it has bounded cliquewidth [LR04]. By a theorem of Courcelle,
Makowsky and Rotics [CMR00], this implies existence of a linear-time algorithm for GI
on difference graphs.
A direct corollary of the Lovász sandwich theorem gives us that the Lovász number
of a perfect graph is the same as its clique number [Lov79]. Since the Lovász number
can be computed in polynomial time, if the weak modular product of two graphs is
perfect, testing if they are isomorphic is polynomial. To this end, we define a new graph
product on bipartite graphs, the very weak modular product. We show that the very
weak modular product of balanced bipartite graphs is perfect only in three trivial cases
(Theorem 2) and as a corollary, the weak modular product is perfect only in these cases
(Corollary 4). Recall that a bipartite graph is balanced when the size of its bipartition
classes is equal. It is clear isomorphism of balanced bipartite graphs is equivalent to the
general case by adding zero-degree vertices.
The paper is structured as follows. In Section 2 we formally define the weak modular
product and re-prove Kozen’s theorem using modern notation. Section 3 contains some
results on bipartite graphs that will be used throughout the paper. In Section 4 we prove
results about bicliques in bipartite graphs which are needed for the main results of the
paper. Section 5 presents the main results of the paper: the IvBE algorithm and the full
characterisation of balanced bipartite graphs whose weak modular product is perfect. In
Section 6 we find the number of bicliques for certain classes of bipartite graphs, including
random bipartite graphs and the extremal cases.

2

The Weak Modular Product

A graph G = (V (G), E(G)) consists of a set V (G) of n vertices and a set of edges
E(G) ⊆ {{ui , uj } : ui , uj ∈ V (G), ui 6= uj }. We consider only finite, undirected graphs.
We write ui ∼ uj to denote that vertices ui and uj are adjacent.

3

The (i, j)th entry of the adjacency matrix of a graph G is defined by

[A(G)]i,j =



1,

if {vi , vj } ∈ E(G);


0,

otherwise.

(1)

We denote by G the complement of G, V (G) = V (G) and ui ∼ uj in G if and only if
ui 6∼ uj in G and ui 6= uj . The union of graphs G and H is the graph G ∪ H with vertex
set V (G ∪ H) = V (G) ∪ V (H) and edge set E(G ∪ H) = E(G) ∪ E(H). The disjoint
union of graphs G and H is the graph G ] H with vertex set V (G ] H) = V (G) ] V (H)
and edge set E(G ] H) = E(G) ] E(H). For a graph G, we denote the disjoint union of
k copies of G by kG.
A graph G0 is a subgraph of another graph G, G0 ⊆ G , if and only if V (G0 ) ⊆ V (G),
and
E(G0 ) ⊆ E(G) and for all {ui , uj } ∈ E(G0 ), ui , uj ∈ V (G0 ).
(2)
Suppose we have a subset of the vertices U ⊆ V (G). An induced subgraph of G, G[U ], is
the graph with vertex set V (G[U ]) = U and edge set
{{ui , uj } | ui , uj ∈ U, {ui , uj } ∈ E(G)}.

(3)

We say G[U ] is induced by U ⊆ V (G).
We now define two closely related graph products. The tensor product of graphs G
and H, denoted by G ⊗ H, has vertex set V (G) × V (H) and an edge {(ui , vj ), (uk , vl )}
if and only if {ui , uk } ∈ E(G) and {vj , vl } ∈ E(H).
The weak modular product (see, e.g., Hammack, Imrich and Klavžar [HIK11]) of
graphs G and H, denoted by G ∇ H, has vertex set V (G ∇ H) = V (G) × V (H) and an
edge {(ui , vj ), (uk , vl )} if and only if
1. either {ui , uk } ∈ E(G) and {vj , vl } ∈ E(H);
2. or {ui , uk } ∈ E(G) and {vj , vl } ∈ E(H).
The next statement is a direct consequence of the definitions of the weak modular
product and the tensor product.
Lemma 1 For graphs G and H,
G ∇ H = G ⊗ H ∪ G ⊗ H.

(4)

Lemma 2 For graphs G and H on n vertices, we have
A(G ∇ H) = A(G ⊗ H) + A(G ⊗ H).

(5)

Proof. Consider the adjacency matrix of G ∇ H, which by Eq. (1) and the definition of

4

the weak modular product has entries given by

[A(G ∇ H)](i−1)n+j,(k−1)n+l =




1,




either {ui , uk } ∈ E(G) and {vj , vl } ∈ E(H);





0,

otherwise

or {ui , uk } ∈ E(G) and {vj , vl } ∈ E(H);

(6)

for all 1 ≤ i, j, k, l ≤ n. For the adjacency matrices of the tensor product, we have
[A(G ⊗ H)](i−1)n+j,(k−1)n+l =



1,

{ui , uk } ∈ E(G) and {vj , vl } ∈ E(H);


0,

otherwise

(7)

and


1,

{ui , uk } ∈ E(G) and {vj , vl } ∈ E(H);
[A(G ⊗ H)](i−1)n+j,(k−1)n+l = 
0, otherwise,

(8)

for all 1 ≤ i, j, k, l ≤ n. Since there cannot be both an edge and a non-edge simultaneously between two vertices, taking the sum of A(G ⊗ H) and A(G ⊗ H) gives Eq. 6, the
desired result.
Given graphs G and H, we say that G and H are isomorphic, G ∼
= H, whenever
there is a bijection f : V (G) → V (H) such that ui ∼ uj if and only if f (ui ) ∼ f (uj ) for
every ui , uj ∈ V (G). A clique is a subset of the vertices of a graph such that every two
distinct vertices in the clique are adjacent. The clique number of a graph G, ω(G), is
the cardinality of its largest clique.
Proposition 1 (Kozen [Koz78]). Let G and H be graphs on n vertices. Then ω(G ∇
H) ≤ n. Moreover, ω(G ∇ H) = n if and only if G ∼
= H.
Proof. To see that there is no clique in G ∇ H larger than n consider the following. First
lay the vertices of G ∇ H in an n × n grid so that the vertex (ui , vj ) is in the same row
as (uk , vl ) if i = k, and in the same column if j = l. Then by the definition of the weak
modular product there can be no edges between vertices in the same row or in the same
column. The vertices of an n-clique will occupy positions on the grid such that no two
vertices are in the same row or column. This restriction means that no larger clique can
exist, as there is no position in the grid where one can place a new vertex such that it
does not share a row or column with any of the vertices already in the clique.
Now suppose there is an n-clique in G∇H. The vertices (ui , vj ) in the clique represent
the bijection ui 7→ vj for all ui ∈ V (G), vj ∈ V (H), which we denote σ. We can see that
σ is an isomorphism because for all ui , uk ∈ V (G), σ(ui ) ∼ σ(uk ) if and only if ui ∼ uk ,
from the definition of the weak modular product. For the converse, suppose that G ∼
= H,
with σ : V (G) → V (H) an isomorphism. Then from the definition of the weak modular

5

product, we will have the collection of edges
{{(ui , σ(ui )), (uk , σ(uk ))} | ui , uk ∈ V (G), uk 6= ui } ⊆ E(G ∇ H).

(9)

This collection of edges induces an n-clique in G ∇ H, so an n-clique exists if and only
if G ∼
= H.
We will find the following well-known result about cliques in tensor products useful,
and include a proof for completeness. We let [k] = {1, 2, . . . , k} for any k ∈ N.
Lemma 3 (Hammack, Imrich and Klavžar [HIK11, Exercise 26.1]). Let G and H be
graphs. Then
ω(G ⊗ H) = min{ω(G), ω(H)}.
(10)
Proof. First, from the definition of the tensor product, for any clique in G ⊗ H, the
corresponding vertices in the factors form a clique, so we have ω(G ⊗ H) ≤ ω(G) and
ω(G ⊗ H) ≤ ω(H). Now suppose without loss of generality ω(G) ≤ ω(H). Let KG ⊆
V (G) induce a maximum clique in G. Now, since ω(G) ≤ ω(H) by assumption there
exists a subset of vertices KH ⊆ V (H) such that |KG | = |KH |. Then, by the definition of
the tensor product, the vertices KG ×KH ⊆ V (G⊗H) induce a clique on G⊗H. Thus we
have ω(G⊗H) ≥ ω(G) when ω(G) ≤ ω(H). A similar argument gives ω(G⊗H) ≥ ω(H)
when ω(H) ≤ ω(G) and the result follows.
An independent set in a graph is a subset of the vertices such that no two vertices in
the subset are adjacent. The independence number of a graph G, α(G), is the cardinality
of its largest independent set. Since a clique in a graph G corresponds to in independent
set in G, we have the following corollary.
Corollary 1 For graphs G and H, we have
ω(G ⊗ H) = min{α(G), α(H)}.

3

(11)

Bipartite Graphs

A graph G on n vertices is said to be bipartite if V (G) = V0 (G) ∪ V1 (G) such that if
ui ∼ uj then ui ∈ V0 (G) and uj ∈ V1 (G) or ui ∈ V1 (G) and uj ∈ V0 (G), for every
ui , uj ∈ V (G). The sets V0 (G) and V1 (G) are said to be the bipartition classes of G. We
can also use a graph invariant to define bipartite graphs. The chromatic number of a
graph χ(G) is the minimum number of colours for which every pair of adjacent vertices
has a different colour. We then say G is bipartite if and only if χ(G) = 2.
The following well-known characterisation is useful to describe the structure of a
bipartite graph. We denote by M T the transpose of a matrix M and write M (m,n) to
specify that M has m rows and n columns, when this is not clear from the context. Let

6

G be a graph on n + m vertices. Then, G is bipartite if and only if there is an ordering
of V (G) such that


(m×n)
(m×m)
0
A
G
,
A(G) =  T (n×m)
(12)
(n×n)
AG
0
where AG is an m × n {0, 1}-matrix and 0(m×m) is the m × n all zeros matrix. We call
the matrix AG the biadjacency matrix of a bipartite graph G.

3.1

Tensor Products of Bipartite Graphs

We will need to make use of some results concerning tensor products of bipartite graphs.
It will be illustrative to state the following established lemma.
Lemma 4 (Hammack, Imrich and Klavžar [HIK11, Section 5.3]). Let G and H be
bipartite graphs. Then, G ⊗ H is bipartite. Moreover, G ⊗ H is bipartite when only one
of G or H is bipartite.
Proposition 2 (Weichsel [Wei62]). Let G and H be connected, bipartite graphs. If at
least one of G and H has an odd cycle, then G ⊗ H is connected. If both G and H are
bipartite, G ⊗ H has exactly two connected components.
Corollary 2 (Hammack, Imrich and Klavžar [HIK11, Corollary 5.10]). A tensor product
of connected graphs is connected if and only if at most one of the factors is bipartite.
The two connected components of G ⊗ H are the bipartite graphs B0,0,1,1 and B0,1,0,1 ,
with vertex-sets V0 (G) × V0 (H) ∪ V1 (G) × V1 (H) and V0 (G) × V1 (H) ∪ V1 (G) × V0 (H),
respectively. There is an ordering of their vertices such that they have the adjacency
matrices


A(B0,0,1,1 ) =  T
AG ⊗ ATH





AG ⊗ AH 

and A(B0,1,1,0 ) = 
AG ⊗ ATH

ATG



⊗ AH 
.

(13)
∼
A natural question to ask is under which conditions B0,0,1,1 = B0,1,1,0 . Such a question was
formulated by Jha, Klavžar and Zmazek [JKZ97] and answered by Hammack [Ham09].
An automorphism of a graph G is an isomorphism from V (G) into V (G). A bipartite
graph is said to be symmetric if there is an automorphism that swaps the bipartition
classes. Hammack showed that for G and H connected bipartite graphs, the two components of G⊗H are isomorphic if and only if at least one of G or H is symmetric [Ham09].

3.2

Tensor Products of Cobipartite Graphs

Here we collect more statements that will prove to be useful later in the text, beginning
with the definition of a cobipartite graph.
Definition 1. (Cobipartite graphs) A graph is cobipartite if it is the complement of a
bipartite graph.
7

Observation 1. For a bipartite graph G, where A(G) can be written as in Eq. (12), its
(cobipartite) complement G can be written as


(m×n)



J (m×m) − I (m×m) J (m×n) − AG
,
A(G) =  (n×m)
T (n×m)
J
− AG
J n×n − I (n×n)

(14)

where J (m×n) is the m × n all-ones matrix and I (n×n) is the n × n identity matrix.
Proof. Use Eq.(12) and the fact that A(G) = J − I − A(G).
Also, note that J (n×n) − I (n×n) = A(Kn ), where Kn is the complete graph on n
vertices.
We shall now evaluate the matrix A(G) ⊗ A(H), for bipartite graphs G and H. Let
the adjacency matrices A(G) and A(H) be as in Eq. (??), with AG being an mG × nG
matrix and AH being an mH × nH matrix. Using Eq. (13), we can write the adjacency
matrix of G ⊗ H as



A(G ⊗ H) =

A(B0,0,1,1 )




A(B0,1,1,0 )



=

 T
AG ⊗ AT
H






AG ⊗ AH

AG ⊗ AT
H



.
T
AG ⊗ AH 


(15)
Note that even if G and H are not connected, we can still write the adjacency matrix of
G ⊗ H in this way. The adjacency matrix of G ⊗ H, using Observation 1 and the same
vertex labelling as in Eq. (15), is
A(G) ⊗ A(H) =




A(KmG ) ⊗ A(KmH ) (J − AG ) ⊗ (J − AH ) A(KmG ) ⊗ (J − AH ) (J − AG ) ⊗ A(KmG )


T
(J − AT

A(KnG ) ⊗ A(KnH )
(J − AT
A(KnH ) ⊗ (J − AT
G ) ⊗ (J − AH )
G ) ⊗ A(KnH )
H) 

.
 A(K ) ⊗ (J − A )
T
T
(J − AG ) ⊗ A(KnH )
A(KmG ) ⊗ A(KnH ) (J − AG ) ⊗ (J − AH )


mH
H
(J − AG ) ⊗ A(KmH ) A(KnG ) ⊗ (J − AT
(J − AG ) ⊗ (J − AT
A(KnG ) ⊗ A(KmH )
H)
H)

(16)
It is useful to note that the matrices A(G ⊗ H) and A(G ⊗ H) (under the vertex labelling
employed in Eq. (15)) have the block structure








mG mH × mG mH mG mH × nG nH mG mH × mG nH mG mH × nG mH
nG nH × mG mH
nG nH × nG nH
nG nH × mG nH
nG nH × nG mH
mG mH × mG nH nG nH × mG nH mG nH × mG nH nG mH × mG nH
mG mH × nG mH nG nH × nG mH mG nH × nG mH nG mH × nG mH





,



(17)

where the entries of the array in Eq. (17) are the sizes of the respective blocks in Eqs. (15)
and (16).
We note that the diagonal blocks of A(G⊗H) are the adjacency matrices of the graphs
Km ⊗ Kn for different values of m and n. These graphs are in fact the complement of
8

the m × n rook’s graph R(m, n), the graph whose vertices are the tiles on an m × n
chessboard and whose edges represent the legal moves of a rook.
Lemma 5 (Hon et. al. [HKL+ 13]) Let m, n ∈ N. Then
K m ⊗ Kn ∼
= R(m, n).

(18)

We therefore call the graph Km ⊗ Kn a m × n co-rook.
Lemma 6 Let m, n ∈ N, with rmin = min{m, n} and rmax = max{m, n}. Then,
ω(R(m, n)) = rmin . Furthermore, there are rmax !/(rmax − rmin )! rmin -cliques in R(m, n).
Proof. The first statement is a direct consequence of Lemma 3 and Lemma 5. For the
second, from the definition of a co-rook, we count the non-attacking positions of rmin
rooks on an m × n chessboard to count the number of rmin -cliques in R(m, n). Without
loss of generality, assume m ≤ n. Start with an empty board and move down the rows
from the top. In the first row, there are n tiles where one can place a rook. In the
second row, there are now n − 1 allowed tiles, so as to avoid the column the first rook
has been placed in. Continuing this procedure, by the mth row, there are (n − m + 1)
allowed positions for a rook to be placed in. Thus in total we have n!/(n − m)! possible
non-attacking configurations in which to place the m rooks, each of which induces an
m-clique in R(m, n). By a similar argument for the case in which m ≥ n, we get the
desired result.

4

Bicliques in Bipartite Graphs

Suppose we have a bipartite graph G with bipartition classes V0 (G) and V1 (G) with
cardinalities m and n respectively. If E(G) is such that every vertex in V0 (G) is adjacent
to every vertex in V1 (G) then we call G a complete bipartite graph, Km,n . A (m0 , n0 )biclique in a graph is a complete bipartite subgraph, Km0 ,n0 , where m0 , n0 ∈ N. We say a
biclique has size k if it contains k vertices. The problem of deciding whether or not there
exists a biclique of certain size in a bipartite graph has been discussed in Garey and
Johnson [GJ79, GT24], where they comment that this is solvable in polynomial time.
We prove this formally in Proposition 3, but first we require some additional notions.
A biclique is maximal if it is not contained in any other biclique. If a graph G has k
maximal bicliques, we say that β(G) = k, where β(G) is the maximal bclique number of
G.
Bicliques in bipartite graphs can be interpreted as an analogue to cliques in general
graphs, in that the definitions are the same, modulo the constraint in the bipartite case
that no edges exist within a given bipartition class. In a similar way, it will be useful
to define a bipartite analogue of the graph complement. Following Giakoumakis and
Vanherpe [GV97], for a bipartite graph G with bipartition classes V0 (G) and V1 (G), its

9

bi-complement, G
E(G

bip

bip

is the graph with V (G

bip

) = V (G) and

) = {{ui , uj } | ui ∈ V0 (G), uj ∈ V1 (G), {ui , uj } ∈
/ E(G)} .

(19)

Observation 2. For G a bipartite graph, the vertices comprising an independent set in
bip
G form a biclique in G and G .
Given a graph G, a set of nodes S ⊆ V (G) is called a vertex cover if for every edge
{ui , uj } ∈ E(G), either ui ∈ S, uj ∈ S, or both. A minimum vertex cover is a vertex
cover of smallest possible cardinality. Furthermore, S ⊆ V (G) is an independent set in
G if and only if V (G) \ S is a vertex cover of G.
A matching in a graph G is a set of edges M ⊆ E(G) such that no edges share
a common vertex. We say M is a maximum matching if it is of maximum possible
cardinality and M is a perfect matching if every vertex in V (G) belongs to an edge in M .
Furthermore, M is an induced matching if it occurs as an induced subgraph of G. Kőnig
established the relationship between maximum matchings and minimum vertex covers
in bipartite graphs in his famous theorem [Kőn31]. Namely, in any bipartite graph, the
number of edges in a maximum matching equals the number of vertices in a minimum
vertex cover. Moreover, the proof of Kőnig’s Theorem provides a way of constructing
the minimum vertex cover from the maximum matching.
We are now in a position to prove existence of a polynomial-time algorithm to find
bicliques of a given size in bipartite graphs.
Proposition 3 Let G be a bipartite graph and let k ≤ |V (G)| be a positive integer.
Then there is a polynomial-time algorithm to decide whether there exists a biclique of
size k in G.
Proof. Since S is a vertex cover, V (G) \ S is an independent set. By Observation 2, an
bip
independent set in G is a biclique in G . We also have
G

bip

bip

=G

(20)

from the definition of the bi-complement. Using the above, a biclique of size |V (G)| − k 0
bip
exists in G if there is a vertex cover of size k 0 in G . If we find the minimum vertex
bip
cover of G , we can check if a biclique of size k or more exists in G by checking if
|S| ≤ k, where S is the minimum vertex cover.
By Kőnig’s Theorem, in a bipartite graph the number of edges in the maximum
matching is the same as the number of vertices in the minimum vertex cover. Finding
the maximum matching of a bipartite graph has a polynomial time algorithm, thus we
have the desired result.
There are numerous efficient algorithms for finding the maximum bipartite matching
on a bipartite graph. Let G be a bipartite graph and n := |V (G)| and e := |E(G)|.
Hopcroft and Karp’s [HK71] celebrated algorithm finds the maximum matching in G in
10

√
O(e n) time. For relatively sparse graphs, this is still the best bound. In the case of a
dense graph, i.e. when e approaches n2 , Mucha and Sandowski [MS04] provide an O(nω )
algorithm, where ω ≤ 2.3727 is the exponent of matrix multiplication. Madry [Mad13]
e 10/7 ) algorithm.
gave a O(n
Lemma 7 Let mG , nG , mH , nH ∈ N. Then,
KmG ,nG ⊗ KmH ,nH ∼
= KmG mH ,nG nH ] KmG nH ,nG mH .

(21)

Proof. Let G = KmG ,nG and H = KmH ,nH . Then we have |V0 (G)| = mG , |V1 (G)| = nG ,
|V0 (H)| = mH and |V1 (H)| = nH . By Proposition 2, since G and H are connected
and bipartite, G ⊗ H has two connected components B0,0,1,1 and B0,1,1,0 with bipartition
classes (V0 (G)×V0 (H), V1 (G)×V1 (H)) and (V0 (G)×V1 (H), V1 (G)×V0 (H)), respectively,
so we have
G ⊗ H = B0,0,1,1 ] B0,1,1,0 .
(22)
We now argue that B0,0,1,1 ∼
= KmG mH ,nG nH . An edge {ui , uj } ∈ E(G) exists for all
ui ∈ V0 (G), uj ∈ V1 (G) since G is complete bipartite. Similarly, an edge {vk , vl } ∈ E(H)
exists for all vk ∈ V0 (H), vl ∈ V1 (H). By the definition of the tensor product, we
then have {w(i,k) , w(j,l) } ∈ E(B0,0,1,1 ) for all {(i, j, k, l) | ui ∈ V0 (G), vk ∈ V0 (H), vk ∈
V0 (H), vl ∈ V1 (H)}. This is a complete bipartite graph with bipartition classes (V0 (G)×
V0 (H), V1 (G) × V1 (H)), which is isomorphic to KmG mH ,nG nH as the first bipartition has
|V0 (G)||V0 (H)| = mG mH vertices and the second has |V1 (G)||V1 (H)| = nG nH . A similar
argument shows that B0,1,1,0 ∼
= KmG nH ,nG mH . The statement then follows after substituting into Eq. (22).
What Lemma 7 means in practice is that taking the tensor product of two complete
bipartite graphs with (mG + nG ) and (mH + nH ) vertices respectively yields two disconnected complete bipartite graphs with (mG mH + nG nH ) and (mG nH + nG mH ) vertices
respectively. Thus, tensor products of graphs containing bicliques will certainly contain
two bicliques of larger size than in the factors. We can make the following statement
about cliques in tensor products.
Lemma 8 Let G and H be bipartite graphs. Then
β(G ⊗ H) = 2β(G)β(H).

(23)

Proof. Let KG and KH be maximal bicliques in G and H respectively. By Lemma 7,
there will be two bicliques in G ⊗ H arising from KG and KH . Both of these bicliques are
maximal by the following: Suppose we increase the size of one of the bicliques in G ⊗ H
by adding a vertex. This implies that there is an additional vertex in both KG and KH
from the definition of the tensor product, but since KG and KH are both maximal, we
have a contradiction.
Now let K be a biclique in G ⊗ H. From Lemma 7, we see that K originates from
a biclique KG in G and a biclique KH in H. If KG and KH are both maximal, then
11

from the above, K is maximal. If either KG or KH are non-maximal, then we have a
contradiction, as increasing the size of KG of KH will increase the size of K, from the
definition of the tensor product. Thus, G ⊗ H has exactly two maximal bicliques arising
from a given pair of maximal bicliques in its factors, and has no additional maximal
bicliques. The result follows.
To prove the next proposition, we introduce the notion of the neighbourhood of
a set of vertices in a graph. For a subset S ⊆ V (G) of the vertices of a graph G,
the neighbourhood of S, NG (S), is the set of vertices adjacent to all vertices in S, i.e.
NG (S) = {ui | {uj , ui } ∈ E for all uj ∈ S}. When the context makes it clear, we omit
the subscript and say N (S).
Proposition 4 Let G and H be bipartite graphs with V0 (G) = V0 (H) := V0 and V1 (G) =
V1 (H) := V1 . Then,
β(G ∪ H) < (β(G) + 1)(β(H) + 1).
(24)
Proof. First we note that any maximal biclique in G or H will be induced by a subset of
vertices in V0 and its neighbourhood. In a slight abuse of notation, we can say without
loss of generality that S ⊆ V0 induces a given maximal biclique, where it is understood
that S ∪ N (S) induces the maximal biclique. Now let k := β(G) and k 0 := β(H) for
brevity. Suppose the sets S1 , S2 , . . . , Sk ⊆ V0 induce all of the maximal bicliques in G
and the sets S10 , S20 , . . . , Sk0 0 ⊆ V0 induce all of the maximal bicliques in H.
We make the following claim: Any maximal biclique in G ∪ H is induced on a set of
vertices of the form Si , Sj0 or Si ∪ Sj0 , for some i ∈ [k], j ∈ [k 0 ]. Since there are k + k 0 + kk 0
sets of this form, the proposition follows as k + k 0 + kk 0 < (k + 1)(k 0 + 1).
It remains to prove the above claim. Call K ⊆ V0 the set of vertices which induces
some maximal biclique in G ∪ H. Note that K must be a superset of a maximal biclique
in either G or H, that is, either K = Si ∪ X for some i ∈ [k] or K = Sj0 ∪ X for
some j ∈ [k 0 ], where X ⊆ V0 . Suppose without loss of generality that K = Si ∪ X,
for some i ∈ [k] and some X ⊆ V0 such that there is no j ∈ [k 0 ] for which X = Sj0 ,
that is, X does not induce a maximal biclique in H. Since K induces a biclique in
G ∪ H, we have that NG (Si ) ∩ NH (X) 6= ∅. Now since X does not induce a maximal
biclique in H by supposition, there exists a subset of vertices X 0 ⊆ V0 \ X such that
NH (X) ⊆ NH (X ∪X 0 ) and we have |NG (Si ) ∩ NH (X ∪ X 0 )| ≥ |NG (Si ) ∩ NH (X)|. Thus,
the set of vertices K ∪ X 0 induces a biclique in G ∪ H. This gives a contradiction if X
is non-empty, since by assumption K induces a maximal biclique in G ∪ H. So for
K = Si ∪ X, if X 6= ∅, then X = Sj0 for some j ∈ [k 0 ] and if X = ∅, then K = Si . Using
a similar argument, when K = Sj0 ∪ X, either X = ∅ or X = Si for some i ∈ [k]. Thus,
the claim holds and the proposition follows.
e
We now define α(G)
as the number of maximal independent sets in a graph G. An
independent set S is maximal if there is no additional vertex u ∈ V (G) \ S that can
be included in S, such that S ∪ {u} is an independent set. To consider the number of

12

bip

maximal bicliques in G , we can use the relationship between maximal independent
bip
sets in G and maximal bicliques in G .
Lemma 9 Let G be a bipartite graph. Then,
bip

β(G

bip

e
) ≤ α(G)
≤ β(G

) + 2.

(25)
bip

Proof. Suppose the subset of vertices U ⊆ V (G) induces a maximal biclique in G .
Then, from the definition of the bi-complement, U forms a maximal independent set in
bip
G, as there is no vertex ui ∈ V (G) \ U such that U ∪ {ui } is a maximal biclique in G .
bip
Thus, to every maximal biclique in G there corresponds a maximal independent set
in G. There can be up to two additional maximal independent sets in G, arising when
bip
either V0 (G) or V1 (G) are not contained in maximal bicliques in G , that is, if there
are no zero-degree vertices in G in one or both of the bipartition classes.

5

Bicliques and Isomorphism

We call a bipartite graph balanced when the cardinalities of the bipartition classes are
the same. It will be convenient to talk about balanced, bipartite graphs on 2n vertices,
such that each bipartition class has n vertices. We can do so without loss of generality
as we can simply add degree-zero vertices to the smaller bipartition class of a bipartite
graph until it is balanced. To simplify the discussion, for bipartite graphs G and H with
bipartition classes (V0 (G), V1 (G)) and (V0 (H), V1 (H)), respectively, we denote by U the
set (V0 (G) × V0 (H)) ∪ (V1 (G) × V1 (H)) and V the set (V0 (G) × V1 (H)) ∪ (V1 (G) × V0 (H)).
Then we have the following result.
Theorem 1 Let G and H be balanced bipartite graphs on 2n vertices, and R0 and R1
be co-rooks in G ∇ H, with both being subgraphs of (G ∇ H)[U] or both being subgraphs
of (G ∇ H)[V]. Then, there is a biclique of size 2n joining an n-clique in R0 and an
n-clique in R1 if and only if G ∼
= H.
Proof. We consider the case when R0 and R1 are subgraphs of (G ∇ H)[U]. The same
argument applies for the (G ∇ H)[V] case, upon interchange of U with V, and V0 (H)
with V1 (H).
We have R0 ⊆ (G ∇ H)[V0 (G) × V0 (H)] and R1 ⊆ (G ∇ H)[V1 (G) × V1 (H)] from
the discussion in Section 3.1. Two vertices (ui , vj ) and (uk , vl ) are adjacent in R0 when
ui 6= uk and vj 6= vl , for ui , uk ∈ V0 (G), vj , vl ∈ V0 (H). Similarly, two vertices (ui , vj ) and
(uk , vl ) are adjacent in R1 when ui 6= uk and vj 6= vl , for ui , uk ∈ V1 (G), vj , vl ∈ V1 (H).
Let σ0 : V0 (G) → V0 (H) and σ1 : V1 (G) → V1 (H) be bijections and let f : vj 7→ j for all
vj ∈ V (H). Then, the n-cliques in R0 , for a given σ0 will be induced on the vertices
{(ui , σ0 (ui )) | ui ∈ V0 (G)}.

13

(26)

Similarly, the n-cliques in R1 , for a given σ1 will be induced on
{(uj , σ1 (uj )) | uj ∈ V1 (G)}.

(27)

So a given pair of n-cliques, one in R0 and one in R1 , can be indexed by the pair of
bijections (σ0 , σ1 ).
(σ0 ,σ1 )
between the n-cliques indexed by σ0 and σ1
Now suppose there is a biclique Kn,n
respectively, that is, we have
(ui , σ0 (ui )) ∼ (uj , σ1 (uj )) for all ui ∈ V0 (G), uj ∈ V1 (G).

(28)

(σ0 ,σ1 )
The graph Kn,n
∪ R0 ∪ R1 forms a 2n-clique since every vertex is connected to every
other vertex. By Proposition 1, G and H are thus isomorphic.
Now suppose G and H are isomorphic with σ : V (G) → V (H) being an isomorphism.
Then either V0 (G) → V0 (H) and V1 (G) → V1 (H) under σ, or V0 (G) → V1 (H) and
V1 (G) → V0 (H). Without loss of generality, we can assume that we have the first
instance as we can just relabel the bipartition classes for this to be true. Let σ0 :
V0 (G) → V0 (H) and σ1 : V1 (G) → V1 (H) be the bijective mappings that act as σ does
on the domains V0 (G) and V1 (G) respectively, that is, σ0 (ui ) = σ(ui ) and σ1 (uj ) = σ(uj )
for all ui ∈ V0 (G), uj ∈ V1 (G). From the definition of the weak modular product, we
have (ui , σ0 (ui )) ∼ (uj , σ1 (uj )) in G ∇ H if and only if either

• ui ∼ uj in G and σ0 (ui ) ∼ σ1 (uj ) in H for ui ∈ V0 (G), uj ∈ V1 (G);
• or ui  uj in G and σ0 (ui )  σ1 (uj ) in H for ui ∈ V0 (G), uj ∈ V1 (G).
Now ui  uj and σ0 (ui )  σ1 (uj ) for all ui ∈ V0 (G), uj ∈ V1 (G) as G and H are
bipartite, so we have (ui , σ0 (ui )) ∼ (uj , σ1 (uj )) for all ui ∈ V0 (G), uj ∈ V1 (G). The
graph induced by this collection of edges has two disjoint vertex subsets, {(ui , σ0 (ui ))}
and {(uj , σ1 (uj ))}, each containing n vertices, where each vertex in a given subset is
connected to every vertex in the other subset. By definition, this is a biclique of size 2n,
(σ0 ,σ1 )
which we call Kn,n
. From Eqs. (26) and (27), we can see that the bipartition classes
(σ0 ,σ1 )
of Kn,n
induce n-cliques in R0 and R1 respectively.
Corollary 3 Let G and H be balanced, bipartite graphs on 2n vertices. An edge in
G ∇ H contributes to a 2n-clique in G ∇ H if and only if it is in (G ∇ H)[U] ] (G ∇ H)[V].
Proof. We can see from the proof of Theorem 1 that any 2n-clique will either be in the
graph (G ∇ H)[U] or (G ∇ H)[V]. Thus any edge in a 2n-clique will be in the disjoint
union of these two graphs.
Theorem 1 and Corollary 3 motivate the definition of a new graph product, defined on
balanced bipartite graphs, where a clique of a certain size is a certificate for isomorphism
for the two graphs.

14

Definition 2. (Very Weak Modular Product). Let G and H be balanced, bipartite graphs
on 2n vertices, with bipartition classes (V0 (G), V1 (G)) and (V0 (H), V1 (H)), respectively.
Then the very weak modular product, G H, is the graph with vertex set V (G H) =
V (G)×V (H) and edges {(ui , vj ), (uk , vl )} ∈ E(G H) if and only if, for all 1 ≤ i, j, k, l ≤
n
1. either {ui , uk } ∈ E(G) and {vj , vl } ∈ E(H);
2. or {ui , uk } ∈ E(G) and {vj , vl } ∈ E(H);
3. and either (ui , vj ), (uk , vl ) ∈ U or (ui , vj ), (uk , vl ) ∈ V,
where as before, U = V0 (G) × V0 (H) ∪ V1 (G) × V1 (H) and V = V0 (G) × V1 (H) ∪ V1 (G) ×
V0 (H).
We now consider the adjacency matrix of G H. First we fix the labelling of the
vertices of G and H such that the adjacency matrix A(G H) uses the same vertex
labelling as Eqs. (15) and (16). Thus A(G H) is a block diagonal matrix, with blocks
(U )
(V)
AG H and AG H (in that order), given by




A(Kn ) ⊗ A(Kn )
AG ⊗ AH + (J − AG ) ⊗ (J − AH )
(U )
AG H =  T
T
T
T
A(Kn ) ⊗ A(Kn )
AG ⊗ AH + (J − AG ) ⊗ (J − AH )
(29a)


T
T
A(Kn ) ⊗ A(Kn )
AG ⊗ AH + (J − AG ) ⊗ (J − AH )
(V)
AG H = 
T
T
A(Kn ) ⊗ A(Kn )
AG ⊗ AH + (J − AG ) ⊗ (J − AH )
(29b)
These blocks represent the graphs (G ∇ H)[U] and (G ∇ H)[V], so we have the following
observations.
Observation 3. For G and H balanced bipartite graphs on 2n vertices,
G

H∼
= (G ∇ H)[U] ] (G ∇ H)[V].

Observation 4. The graphs (G ∇ H)[U] and (G ∇ H)[V] are connected, that is, G
has exactly two connected components.

(30)
H

The previous observation can be deduced from Lemma 2 and the adjacency matrix
of G H.
Observation 5. Let R1 and R2 be the co-rooks in a connected component of G H.
There is a 2n-clique between an n-clique in R1 and an n-clique in R2 if and only if
G∼
= H.
Observation 5 directly follows from Theorem 1. Each connected component of the
graph G H is the disjoint union of two co-rooks R(n2 , n2 ), with the edges of a bipartite
graph joining the vertices of the two co-rooks. Note that a biclique of size 2n can exist
15

1

1

1

1

1

1

1

1

2

2

2

2

2

2

2

2

3

3

3

3

3

3

3

3

(1,1)

(1,1)

(1 ,1 )

(1 ,1 )

(1,1 )

(1,1 )

(1 ,1)

(1 ,1)

(1,2)

(1,2)

(1 ,2 )

(1 ,2 )

(1,2 )

(1,2 )

(1 ,2)

(1 ,2)

(1,3)

(1,3)

(1 ,3 )

(1 ,3 )

(1,3 )

(1,3 )

(1 ,3)

(1 ,3)

(2,1)

(2,1)

(2 ,1 )

(2 ,1 )

(2,1 )

(2,1 )

(2 ,1)

(2 ,1)

(2,2)

(2,2)

(2 ,2 )

(2 ,2 )

(2,2 )

(2,2 )

(2 ,2)

(2 ,2)

(2,3)

(2,3)

(2 ,3 )

(2 ,3 )

(2,3 )

(2,3 )

(2 ,3)

(2 ,3)

(3,1)

(3,1)

(3 ,1 )

(3 ,1 )

(3,1 )

(3,1 )

(3 ,1)

(3 ,1)

(3,2)

(3,2)

(3 ,2 )

(3 ,2 )

(3,2 )

(3,2 )

(3 ,2)

(3 ,2)

(3,3)

(3,3)

(3 ,3 )

(3 ,3 )

(3,3 )

(3,3 )

(3 ,3)

(3 ,3)

Figure 1: Illustration of the case in which the very weak modular product between two balanced,
bipartite, non-isomorphic graphs on 2n = 6 vertices has bicliques of size 2n between pairs of
co-rooks, but not between cliques in these co-rooks. The vertices comprising the bicliques are
circled.
1

1

1

1

2

2

2

2



(1,1)

(1 ,1 )

(1,1 )

(1 ,1)

(1,2)

(1 ,2 )

(1,2 )

(1 ,2)

(2,1)

(2 ,1 )

(2,1 )

(2 ,1)

(2,2)

(2 ,2 )

(2,2 )

(2 ,2)

Figure 2: Two balanced, bipartite graphs on n = 2 vertices for which the very weak modular
product between them does not contain Kn,n as a subgraph.

between the co-rooks of two balanced, bipartite graphs G and H, for which G  H, just
not between n-cliques in the co-rooks. An example of this is shown in Figure 1.
On the other hand, one might be lead to think that there might always be a biclique
of size 2n in G H.
Proposition 5 Let Bn,n be the set of balanced, bipartite graphs on 2n vertices. Then
there exist G, H ∈ Bn,n such that neither of the connected components of G H contains
Kn,n as a subgraph.
An example of such G and H is shown Figure 2.

16

5.1

Perfect Graphs and the Very Weak Modular Product

A graph is perfect if the chromatic number of every induced subgraph equals the clique
number of the subgraph. Lovász’s famous ‘sandwich theorem’ states that for any graph
G, ω(G) ≤ ϑ(G) ≤ χ(G), where ϑ(G) is the Lovász number of the graph G, which can
be computed in polynomial time [Lov79]. Since for a perfect graph G, ω(G) = χ(G), by
the sandwich theorem we have that ω(G) = ϑ(G). Now suppose for certain graphs G
and H on n vertices, their weak modular product G ∇ H was perfect. Then, deciding if
G∼
= H would be easy, by virtue of the Lovász number giving us the maximum clique in
G ∇ H in time polynomial in n. In the same way, for balanced bipartite graphs G and
H whose very weak modular product G H were perfect, deciding if G ∼
= H would be
easy. In Theorem 2 below we characterise the cases in which this is true, which turn out
to be trivial.
We first need the following. The co-rook R(m, n) is in fact perfect [HKL+ 13], as is
any bipartite graph, thus G H is the union of perfect graphs. Cameron, Edmonds and
Lovász [CEL86] characterised the conditions under which the union of perfect graphs is
perfect, which we state without proof.
Proposition 6 (Cameron, Edmonds and Lovász [CEL86, Theorem 10 ]) Let G1 and G2
be perfect graphs and G := G1 ∪ G2 be their union with V (G1 ) = V (G2 ) = V (G) .
Suppose that for any ui , uj , uk ∈ V (G), {ui , uj } ∈ E(G1 ) and {uj , uk } ∈ E(G2 ) implies
that {ui , uk } ∈ E(G). Then, G is perfect.
Theorem 2 Let G and H be balanced, bipartite graphs on 2n vertices, with n ≥ 2.
Then, G H is perfect if and only if either
1. G and H are both the complete bipartite graph Kn,n ;
2. G and H are both the empty graph K 2n ;
3. One of G, H is the complete bipartite graph Kn,n and the other the empty graph
K 2n .
Proof. Each connected component of the graph G H is comprised of the disjoint union of
two co-rooks, R(n2 , n2 ) with the edges of a bipartite graph Bn2 ,n2 , adjoining the vertices
of the co-rooks. We show that a connected component of G H is perfect if and only
if Bn2 ,n2 ∼
= K 2n2 . Then we show that Bn2 ,n2 ∼
= Kn2 ,n2 if and only if
= Kn2 ,n2 or Bn2 ,n2 ∼
G, H ∼
= Kn,n or G, H ∼
= K 2n and Bn2 ,n2 ∼
= K 2n2 if and only if one of G, H is isomorphic
to Kn,n and the other K 2n . Taken together, the theorem is thus proved, as a graph
whose connected components are perfect is perfect.
Take one of the connected components of G H and call the first co-rook R1 and the
second R2 . The bipartition classes of Bn2 ,n2 are the vertex sets of R1 and R2 . Suppose we
have a vertex (ui , vj ) in R1 , adjacent to a vertex (uk , vl ) in R2 , that is, {(ui , vj ), (uk , vl )}
is an edge in Bn2 ,n2 . Now (uk , vl ) ∼ (uk0 , vl0 ) in R2 , for all k 0 and l0 such that k 0 6= k and
l0 6= l from the definition of a co-rook. By Proposition 6, for G H to be perfect, we
17

must have (ui , vj ) ∼ (uk0 , vl0 ) in Bn2 ,n2 , for all 1 ≤ k 0 , l0 ≤ n such that k 0 6= k and l0 6= l,
since the only edges connecting vertices in R1 and R2 are in Bn2 ,n2 . Now for each of the
(uk0 , vl0 ), again by Proposition 6 (ui , vj ) will have to be adjacent to all of the neighbours
of (uk0 , vl0 ) to ensure perfection of G H. Since R2 is connected by Lemma 2, continuing
recursively we see that if (ui , vj ) in R1 is adjacent to a single vertex (uk , vl ) in R2 , it
must be adjacent to all of the vertices in R2 for G H to be perfect. By symmetry, if a
vertex in R2 is adjacent to R1 , it must be adjacent to all of the vertices in R1 for G H
to be perfect. Thus any Bn2 ,n2 with non-empty edge set must be a complete bipartite
graph for G H to be perfect. The disjoint union of perfect graphs is perfect so if the
edge set of Bn2 ,n2 is empty, G H is perfect.
We now show that Bn2 ,n2 ∼
= Kn2 ,n2 if and only if G, H ∼
= Kn,n or G, H ∼
= K 2n and
Bn2 ,n2 ∼
= K 2n2 if and only if one of G, H is isomorphic to Kn,n and the other K 2n .
Inspection of Eq. (29) shows that proving the statement is equivalent to proving that

AG ⊗ AH + (J (n×n) − AG ) ⊗ (J (n×n) − AH ) =


2
2


J (n ×n ) ,






2
2


0(n ×n ) ,







iff AG = AH = J (n×n) ,
or AG = AH = 0(n×n) ;
iff AG = J (n×n) , AH = 0(n×n) ,
or AG = 0(n×n) , AH = J (n×n) ,
(31)

with an equivalent statement applying to the matrix
ATG ⊗ AH + (J (n×n) − ATG ) ⊗ (J (n×n) − AH ),

(32)

where AG and AH are the biadjacency matrices of G and H respectively. We consider
the first case without loss of generality. Sufficiency can be straightforwardly seen from
Eq. (31), so we show necessity. Call the left hand side of Eq. (31) MU , which can be
written in block form as
[AG ]1,1 AH + (1 − [AG ]1,1 )(J (n×n) − AH ) · · · [AG ]1,n AH + (1 − [AG ]1,n )(J (n×n) − AH )


..
..
..

.
.
.
.






[AG ]n,1 AH + (1 − [AG ]n,1 )(J (n×n) − AH ) · · · [AG ]n,n AH + (1 − [AG ]n,n )(J (n×n) − AH )

(33)
th

Consider the (i, j)

block of MU ,

[AG ]i,j AH + (1 − [AG ]i,j )(J (n×n) − AH ) =



AH ,

J (n×n)

if [AG ]i,j = 1;
− AH , if [AG ]i,j = 0.

(34)

Observe that all the elements of MU can only be the same if all of the elements of AG are
the same, as otherwise MU would be a block matrix comprised of differing blocks. Now
suppose all the elements of AG are equal. Then for all of the elements of MU to be equal,
all of the elements of AH have to be the same as each other, since MU is made up of
repeating blocks of either AH , or J (n×n) − AH . Together, we have that all of the elements

18

of MU are the same only if all of the elements in AG are equal and all of the elements
in AH are equal. From Eq. (34) we can see that MU is the all-ones matrix only if all of
the elements of both AG and AH are the same, i.e. are both all-ones or both all-zeroes,
otherwise MU will be the all-zeroes matrix. Thus we have that Bn2 ,n2 ∼
= Kn2 ,n2 if and
only if G, H ∼
= K 2n2 if and only if one of G, H is
= Kn,n or G, H ∼
= K 2n , and Bn2 ,n2 ∼
Kn,n and the other K 2n .
Corollary 4 Let G and H be balanced, bipartite graphs on 2n vertices, with n ≥ 2.
Then, G ∇ H is perfect if and only if either
1. G and H are both the complete bipartite graph Kn,n ;
2. G and H are both the empty graph K 2n ;
3. One of G, H is the complete bipartite graph Kn,n and the other the empty graph
K 2n .
Proof. Since G H ⊂ G ∇ H, the only possible cases where G ∇ H can be perfect are
the cases when G H is perfect, which are the three cases given. We show that G ∇ H
is perfect in each of these cases. For case 1., using Eqs. (15) and (16), one can see that
A(G ∇ H) = A(G H) implying G ∇ H ∼
= G H, which is perfect. For both cases
2. and 3. (in case 3. assume without loss of generality that G = Kn,n and H = K 2n )
one can readily verify using Eqs. (15) and (16) that A(G ∇ H) = [ 11 11 ] ⊗ A(X), where
A(X) = A((G H)[U]) = A((G H)[V]). This corresponds to taking the disjoint union
2X, calling the connected components X1 and X2 , then drawing edges {ui , vj } for all
ui ∈ V (X1 ), vj ∈ V (X2 ) such that ui ∼ uj (or equivalently vi ∼ vj ). Since X1 and X2
are perfect, using Proposition 6 we have the result.

5.2

Isomorphism via Biclique Enumeration: The Algorithm

We present our algorithm for isomorphism of bipartite graphs, Isomorphism via Biclique
Enumeration (IvBE), shown in Algorithm 1. We use the MBEA algorithm of Zhang et.
al. [ZPR+ 14] for enumerating all of the maximal bicliques of a bipartite graph G, which
we denote mbea(G).
Proposition 7 [ZPR+ 14, Theorem 2] Let G be a bipartite graph with |E(G)| = e.
There is an algorithm, mbea(G), that finds all the maximal bicliques in G with runtime
O(eβ(G)).
Theorem 3 Let G and H be balanced, bipartite graphs on 2n vertices, each having
e edges. Then, given G and H as input, IvBE (Algorithm 1) returns an isomorphism
σ : V (G) → V (H) if G ∼
= H and returns not isomorphic otherwise. Moreover, IvBE
bip
bip
2
runs in time O(β(Ω)en ), where Ω := G ⊗ H ∪ G ⊗ H .

19

Algorithm 1 Isomorphism via Biclique Enumeration (IvBE)
Input: Balanced, bipartite graphs on 2n vertices G and H, with V (G) =
{u1 , . . . , u2n } and V (H) = {v1 , . . . , v2n }.
Output: A bijection σ : V (G) → V (H) if G ∼
= H, or the certificate not
isomorphic if G  H.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
1:
2:
3:
4:
5:
6:
7:

bip

bip

Construct the graph Ω := G⊗H ∪G ⊗H , where V (Ω) = V (G)×V (H).
Enumerate the maximal bicliques BΩ ← mbea(Ω).
if {B ∈ BΩ : |V0 (B)| = |V1 (B)| = n} = ∅ then
return not isomorphic
end if
for all B ∈ BΩ : |V0 (B)| = |V1 (B)| = n do
if is_co-rook_clique(Ω, V0 (B)) ∧ is_co-rook_clique(Ω, V1 (B))
then
Instantiate bijection σ : V (G) → V (H).
for all i such that (ui , vj ) ∈ V0 (B) do
Add σ : ui 7→ vj , where ui ∈ V (G), vj ∈ V (H).
end for
for all i such that (ui , vj ) ∈ V1 (B) do
Add σ : ui 7→ vj , where ui ∈ V (G), vj ∈ V (H).
end for
return σ.
else
return not isomorphic
end if
end for
function is_co-rook_clique(Ω, S ⊆ V (Ω))
if (∀ (ui , vj ), (uk , vl ) ∈ S s.t. (ui , vj ) 6= (uk , vl ), {(ui , vj ), (uk , vl )} ∈
E(G H) then
return true
else
return false
end if
end function

Proof. First, observe that G H can be produced by taking the union of Ω with corooks on the bipartition classes of the two connected components of Ω, that is, G H =
Ω ∪ 4R(n, n) = Ω ∪ 4(Kn ⊗ Kn ) under the appropriate vertex labelling. Recall from
Observation 5 that G ∼
= H if and only if there is a (n, n)-biclique joining the n-cliques
in the co-rooks of a connected component of G H.
First, suppose G ∼
= H with σ 0 : V (G) → V (H) an isomorphism. Then by Observa-

20

tion 5, at line 7 in Algorithm 1 the (n, n)-biclique B encoding σ 0 induces n-cliques in the
co-rooks within G H. The lines 8-15 then write down and return σ 0 as the bijection
σ. Now suppose G  H. Either we have the situation as in Figure 2 where there are
no (n, n)-bicliques in Ω and the algorithm returns not isomprphic at line 4. More
commonly there exist (n, n)-bicliques in Ω, but they do not satisfy the necessary and
sufficient conditions of Observation 5 for isomorphism. In this case, Algorithm 1 returns
not isomorphic at line 17. The function is_co-rook_clique checks that under the
chosen vertex labelling, a set S of vertices in Ω induces a clique in a co-rook of G H.
The if statement is equivalent to checking pairwise adjacency of the vertices S in G H,
which is polynomial in |S| = n in the cases where the function is used.
The runtime of the algorithm is O(β(Ω)en2 ), with the O(β(Ω)e) factor arising from
enumerating the maximal bicliques in Ω using mbea(Ω) and the O(n2 ) factor from the
is_co-rook_clique function.

6

Counting Maximal Bicliques in Bipartite Graphs

We now consider graphs for which we can directly enumerate the number of maximal
bicliques. For example, consider the classes of bipartite graph for which the number of
maximal bicliques is polynomial in the number of vertices. In such an instance, we know
that we can find all the maximal bicliques in polynomial time, by Proposition 7. We
characterise the number of maximal bicliques in certain graphs here, considering first
the extremal cases.

6.1

Extremal Cases

For n ≥ 2, define the graph Bn , where for even n, Bn is the graph K n2 , n2 with a perfect
matching removed. For odd n, Bn is the graph Bn−1 with an additional vertex added,
which is adjacent to all of the vertices in one of the bipartition classes of Bn−1 . We give
examples of Bn in Figure 3 for clarification. In addition, if n is even we call Bn a crown
graph. We then have the following result.
Proposition 8 Let G be a bipartite graph on n ≥ 4 vertices. Then,
β(G) ≤



2b n2 c
bn
c
2


2

− 2, n even;
− 1, n odd.

(35)

Moreover, this bound is saturated if and only if G ∼
= Bn .
Proof. We proceed by induction on n, where we shall assume the hypothesis for even
n, then show that the hypothesis is consequently true for n + 1 and n + 2. As in the
proof of Proposition 4, any biclique in G can be uniquely described as being induced on
a subset of vertices S ⊆ V0 (G), as the associated biclique will be induced on the vertices

21

S ∪ NG (S). Suppose n = 2s, where s ≥ 2, and Bn is the unique graph on n vertices
n+1
n
n
with the maximum possible number of bicliques, 2b 2 c − 2. Now 2b 2 c = 2b 2 c since n
is even. Let us now add a vertex u1 to this graph (without loss of generality, add it to
V1 (Bn )). We now call this graph H and wish to increase its number of maximal bicliques
by 1. Since in this graph the subsets S ∪ NH (S) for all ∅ ⊂ S ⊂ V0 (H) already induce
maximal bicliques, the only maximal biclique we can add is V0 (H) ∪ NH (V0 (H)). Now
NBn (V0 (Bn )) = ∅ so the only way to simultaneously have non-empty NH (V0 (H)) and
not to remove existing maximal bicliques is to draw edges between u1 and each member
of V0 (H), giving precisely the graph Bn+1 .
Now we add a new vertex u2 to V0 (H) and will show that the unique graph which
maximises the number of maximal bicliques is Bn+2 . We have that for all sets S such
that ∅ ⊂ S ⊆ V0 (H) \ {u2 }, the set S ∪ NH (S) induces a maximal biclique so adding or
removing edges between pairs of vertices in V (H) \ {u2 } would decrease the number of
maximal bicliques. Thus we can only add edges between u2 and the elements of V1 (H).
We claim that our bound is saturated only when n edges are added, specifically the
edges {{u2 , u0i } | u0i ∈ V1 (H) \ {u1 }}. In this case, every set of the form S ∪ N (S) for
all ∅ ⊂ S ⊂ V1 (H) is a maximal biclique and the bound is saturated. We can see that
this is the only such case from the following three alternative scenarios: i. Every edge
{{u2 , u0i } | u0i ∈ V1 (H)} is placed. ii. n edges are placed, including {u2 , u1 }. iii. Fewer
than n edges are placed.
• Case i. Suppose every possible edge between u2 and every element of V1 (H) is
added. Now, u2 is added to every existing maximal biclique since it is adjacent to
every vertex in V1 (H), so our graph has 2n+1 − 1 maximal bicliques and our bound
for n + 2 is not saturated.
• Case ii. Suppose we draw the edge {u1 , u2 } and n − 1 further edges between u2
and elements of V1 (H) \ {u1 }. Now, similar to in case i., u1 is added to every
maximal biclique induced on subsets of V0 (H) \ {u1 }, so our graph has 2n+1 − 1
maximal bicliques and does not saturate the bound. The n − 1 additional edges
only selectively add u2 to already existing maximal bicliques, so do not increase
β(H).
• Case iii. Suppose fewer than n edges are drawn between u2 and V1 (H) \ {u1 }.
Then there will be at least one subset S satisfying {u2 } ⊂ S ⊂ V0 (H) for which
NH (S) = ∅ as there will be no edge between u2 and NH (S \ {u2 }), for NH (S \ {u2 })

Figure 3: The graphs B8 , B9 and T9 .

22

a single vertex. Since not every subset ∅ ⊂ S ⊂ V0 (H) induces a maximal biclique
the bound is not saturated.
n

This also shows that for even n the maximum β(G) = 2b 2 c − 2, unlike in the odd n
case. We now have that only the graph Bn+2 saturates the bound for n + 2 vertices, as
required. It is straightforward to check the inductive hypothesis for 4 vertices, i.e. that
B4 ∼
= 2K2 is the only graph that saturates the bound, and the result follows.
We note that for an n-vertex bipartite graph G, Prisner [Pri00] provides an upper
bound for β(G) of 2n/2 , with Bn for even n being the extremal case. This is consistent
with Proposition 8 because his definition of a biclique allows bicliques with empty bipartition classes and he does not consider the odd n case, since it does not saturate his
bound.
We can also characterise the bipartite graphs which maximise the number of maximal
e
independent sets in a graph, α(G).
For odd n, define Tn as the graph obtained by taking
n
b 2 cK2 , then adding an additional vertex, which is adjacent to exactly one vertex in each
K2 . An example is shown in Figure 3. Now for n ≥ 2 and 0 ≤ r ≤ b n2 c define the graph


 n K2 ,

n even;
0
Bn,r
= 2
rK2 ] T2 n−1 −r +1 , n odd.
(
)

(36)

2

e
Liu gave [Liu93] the following bound on α(G)
for bipartite G.

Proposition 9 [Liu93, Theorem 2.1]. Let G be a bipartite graph on n vertices. Then,
n

e
α(G)
≤ 2b 2 c .

(37)

0
for any 0 ≤ r ≤ b n2 c.
Moreover, this bound is saturated if and only if G ∼
= Bn,r

Observe that Bn

6.2

bip

bip
0
0
∼
for even n and Bn ∼
for odd n.
= Bn,r
= Bn,0

Maximal Bicliques in Random Bipartite Graphs

We can also consider the number of maximal bicliques in random bipartite graphs. We
define a probability distribution over bipartite graphs on m + n vertices as follows:
Consider the independent random variables Xi,j taking the values

Xi,j =



1,

with probability p;


0,

with probability 1 − p.

(38)

for i ∈ [m], j ∈ [n] and p ∈ [0, 1]. A bipartite graph G drawn from the distribution
G(m, n, p) has |V0 (G)| = m, |V1 (G)| = n and edge set {{ui , vj } | ui ∈ V0 (G), vj ∈
V1 (G), Xi,j = 1}. A bipartite graph G drawn from G(m, n, p), is an Erdős-Rényi bipartite
graph, which we denote by G ∼ G(m, n, p). We have the following result.
23

Lemma 10 Let m, n ∈ N and p ∈ [0, 1]. Then,
E

G∼G(m,n,p)

[β(G)] =

m X
n
X

!

pkl (1 − pl )m−k (1 − pk )n−l

k=1 l=1

m
k

!

n
.
l

(39)

Proof. First, let ind(A) be the indicator variable for some event A. We then make the
observation that
E

[β(G)] =

G∼G(m,n,p)

X

X

E[ind(T ∪ U is a maximal biclique)]

∅⊂T ⊆V0 (G) ∅⊂U ⊆V1 (G)

=

X

X

Pr [T ∪ U is a maximal biclique]

∅⊂T ⊆V0 (G) ∅⊂U ⊆V1 (G)

X

Pr [T ∪ U is a biclique] ·
∅⊂T ⊆V0 (G)
Pr [T ∪ U is maximal | T ∪ U is a biclique] .
∅⊂U ⊆V1 (G)
(40)
Suppose we have G ∼ G(m, n, p), ∅ ⊂ T ⊆ V0 (G) and ∅ ⊂ U ⊆ V1 (G), with |T | = k and
|U | = l. Then,
Pr [T ∪ U is a biclique] = pkl ,
(41)
=

from the definition of G and the fact that there are k · l possible edges in T ∪ U . We also
have
Pr [T ∪ U is maximal | T ∪ U is a biclique] =
1 − Pr [T ∪ U is not maximal | T ∪ U is a biclique] . (42)
The statement that T ∪ U is not maximal is equivalent to saying that there exist vertices
either ui ∈ V0 (G) \ T or vj ∈ V1 (G) \ U that can be added to T ∪ U and it remain a
biclique. We have using the inclusion-exclusion principle,
Pr [T ∪ U is not maximal | T ∪ U is a biclique]



[

= Pr 

{u} ∪ T ∪ U is a biclique

u∈V (G)\(T ∪U )

=

(−1)|S|+1 Pr [S ∪ T ∪ U is a biclique]

X

∅⊂S⊆∈V (G)\(T ∪U )

=

X

(−1)|T

0 |+|U 0 |+1

p|T

0 |l+|U 0 |k

+1

∅⊆T 0 ⊆V0 (G)\T
∅⊆U 0 ⊆V1 (G)\U

=

m−k
n−l
X X

(−1)

i+j+1

i=0 j=0

24

m−k
i

!

!

n − l il+jk
p
+ 1.
j

(43)

We thus have from Eq. (42) that
Pr [T ∪ U is maximal | T ∪ U is a biclique]
=

m−k
n−l
X X

(−1)

i=0 j=0

=

m−k
X

i+j

m−k
i

!

!

n − l il+jk
p
j

! 



n−l
m − k il X
n − l jk  (44)
(−1)i
p ·
(−1)j
p
i
j
i=0
j=0

!

!

= (1 − pl )m−k · (1 − pk )n−l
Substituting into Eq. (40) along with Eq. (41) yields
E

[β(G)] =

G∼G(m,n,p)

X

p|T ||U | (1 − p|U | )m−|T | · (1 − p|T | )n−|U |

X

∅⊂T ⊆V0 (G) ∅⊂U ⊆V1 (G)

=

m X
n
X

kl

l m−k

p (1 − p )

(1 − p )

k=1 l=1

6.3

k n−l

m
k

!

!

n
.
l

(45)

Graphs with Polynomial Number of Maximal Bicliques and
IvBE

Prisner [Pri00] provides a sufficient condition for the number of maximal bicliques in a
graph to be polynomial.
Proposition 10 [Pri00, Theorem 3.3] For every integer j, if a bipartite graph G does not
contain any induced B2j , then it contains at most (|V0 (G)||V1 (G)|)j−1 maximal bicliques.
Corollary 5 For every integer j, if a bipartite graph G does not contain any induced
jK2 , then it contains at most (|V0 (G)||V1 (G)|)j−1 + 2 maximal independent sets.
Proof. The condition that G does not contain any induced jK2 is equivalent to the
bip
bip
condition that G does not contain any induced B2j . If G does not contain any
bip
induced B2j , then by Proposition 10 G contains at most (|V0 (G)||V1 (G)|)j−1 maximal
bicliques. Using Lemma 9 gives the result.
Observe that the condition in Corollary 5 is equivalent to saying that G does not
contain an induced matching on 2j vertices and the condition in Proposition 10 is equivalent to saying that G does not contain an induced crown on 2j vertices. For a graph G,
let mind (G) be the largest induced matching in G and let cind (G) be the largest induced
crown in G. We are now in a position to state the following result.
Proposition 11 Let Γ be the class of balanced, bipartite graphs that satisfy the following: For any G ∈ Γ , mind (G) = O(poly log(n)) and cind (G) = O(poly log(n)), where
n = |V (G)|. Then, for any G, H ∈ Γ with |V (G)| = |V (H)| = 2n, deciding if G ∼
=H
O(poly log(n))
takes time 2
, using the IvBE algorithm.
25

bip

bip

Proof. We claim that there are 2O(poly log(n)) maximal bicliques in Ω := G⊗H∪G ⊗H ,
where V (Ω) = V (G H). Using IvBE we can check if G ∼
= H in time O(n2 e)·2O(poly log(n)) .
Since e = O(n2 ) we have runtime O(n4 ) · 2O(poly log(n)) = 2O(poly log(n)) .
Now it remains to justify the earlier claim that β(Ω) = 2O(poly log(n)) . Proposition 10,
bip
bip
Corollary 5 and Lemma 9 give us that G, G , H and H each have a quasi-polynomial
number of maximal bicliques, as (n2 )O(poly log(n)) = nO(poly log(n)) = 2O(poly log(n)) . Lemma 8
ensures that there are a quasi-polynomial number of maximal bicliques in G ⊗ H and
bip
bip
bip
bip
G ⊗H . From Proposition 4, the number of maximal bicliques in G⊗H∪G ⊗H =
Ω is quasi-polynomial in n. Thus, the claim is proven and the result follows.
Proposition 10 and Corollary 5 suggest a class of graphs for which the IvBE algorithm
is polynomial.
Proposition 12 Let Γ be the class of 2K2 -free balanced, bipartite graphs, that is, the
class of balanced, bipartite graphs whose members do not contain 2K2 as an induced
subgraph. Then, for any G, H ∈ Γ such that |V (G)| = |V (H)| = n, IvBE decides if
G∼
= H in time polynomial in n.
Proof. From Proposition 10 and Corollary 5, we have that the number of maximal bicliques and maximal independent sets in G and H are polynomial (in fact quadratic) in
n, since 2K2 ∼
= B4 . We also have from Lemma 9, Lemma 8 and Proposition 4 that the
bip
bip
graph Ω = G ⊗ H ∪ G ⊗ H has a polynomial number of maximal bicliques. Since
the runtime of IvBE has runtime O(β(Ω)en2 ) from Theorem 3 and e = O(n2 ), the result
follows.

7

Conclusion

We have seen that investigating the combinatorics of the weak modular product of bipartite graphs can lead to some insights into using the clique number for isomorphism.
Some open questions remain. For instance, here we have characterised the cases where
the weak modular product of bipartite graphs is perfect. It would be interesting to extend this characterisation to general graphs and/or to other graph subclasses, as using
the Lovász number of the weak modular product graph would yield an efficient algorithm
for GI in these cases.
Furthermore, we have approached the clique number question itself purely from a
combinatorial viewpoint. It may prove useful to look into approximation schemes for
the clique number in conjunction with the weak modular product to investigate GI. It is
known that for all  > 0, there can be no polynomial time algorithm that approximates
the maximum clique of a general graph on n vertices to within a factor better than
√
O(n1− ) unless P = NP [ZD06]. However, there is an O( n)-approximation algorithm
for the dual problem of finding the independence number, when specialised to the union of
perfect graphs [CPRS10]. The very weak modular product of bipartite graphs constitutes
a union of perfect graphs so a modification of this algorithm could be a starting point.
26

Acknowledgements
We would like to thank Sandi Klavžar for comments on the text and for observing that
Lemma 3 and Lemma 4 are known results. Thanks to Antonios Varvitsiotis for his
many useful comments on the style of the paper and for a correction of the proof of
Lemma 3.

References
[Bab15]

L. Babai. Graph Isomorphism in Quasipolynomial Time (2015). arXiv:
1512.03547.

[BJP+ 09] E. J. Baker et al. Ontological discovery environment: A system for integrating
gene-phenotype associations. Genomics, 94, 377 (2009).
[CEL86]

K. Cameron, J. Edmonds and L. Lovász. A note on perfect graphs. Period.
Math. Hungarica, 17, 173 (1986).

[CFSV04] D. Conte, P. Foggia, C. Sansone and M. Vento. Thirty Years of Graph Matching in Pattern Recognition. Int. J. Pattern Recognit. Artif. Intell., 18, 265
(2004).
[CL07]

E. J. Chesler and M. A. Langston. Combinatorial Genetic Regulatory Network Analysis Tools for High Throughput Transcriptomic Data. In Syst. Biol.
Regul. Genomics, 150–165 (2007).

[CMR00] B. Courcelle, J. A. Makowsky and U. Rotics. Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width. Theory Comput. Syst.,
33, 125 (2000).
[CPRS10] V. T. Chakaravarthy, V. Pandit, S. Roy and Y. Sabharwal. Finding Independent Sets in Unions of Perfect Graphs. DROPS-IDN/2868, 8 (2010).
[GJ79]

M. R. Garey and D. S. Johnson. Computers and intractability : a guide to
the theory of NP-completeness. W.H. Freeman (1979).

[GMW91] O. Goldreich, S. Micali and A. Wigderson. Proofs that yield nothing but their
validity or all languages in NP have zero-knowledge proof systems. J. ACM,
38, 690 (1991).
[Gro10]

M. Grohe. Fixed-Point Definability and Polynomial Time on Graphs with
Excluded Minors. In 2010 25th Annu. IEEE Symp. Log. Comput. Sci., 179–
188 (2010).

[GV97]

V. Giakoumakis and J.-M. Vanherpe. Bi-complement Reducible Graphs. Adv.
Appl. Math., 18, 389 (1997).
27

[Ham09]

R. H. Hammack. Proof of a conjecture concerning the direct product of bipartite graphs. Eur. J. Comb., 30, 1114 (2009).

[HIK11]

R. H. Hammack, W. Imrich and S. Klavžar. Handbook of product graphs.
CRC Press (2011).

[HK71]

J. E. Hopcroft and R. M. Karp. A n5/2 algorithm for maximum matchings
in bipartite graphs. In 12th Annu. Symp. Switch. Autom. Theory, 122–125
(1971).

[HKL+ 13] W.-K. Hon et al. Independent Set in Categorical Products of Cographs and
Splitgraphs (2013). arXiv:1305.4237.
[HPS90]

P. L. Hammer, U. N. Peled and X. Sun. Difference graphs. Discret. Appl.
Math., 28, 35 (1990).

[JKZ97]

P. K. Jha, S. Klavžar and B. Zmazek. Isomorphic components of Kronecker
product of bipartite graphs. Discuss. Math. Graph Theory, 17, 301 (1997).

[Kőn31]

D. Kőnig. Gráfok és mátrixok. Mat. és Fiz. Lapok, 38, 116 (1931).

[Koz78]

D. Kozen. A clique problem equivalent to graph isomorphism. ACM SIGACT
News, 10, 50 (1978).

[Liu93]

J. Liu. Maximal independent sets in bipartite graphs. J. Graph Theory, 17,
495 (1993).

[Lov79]

L. Lovász. On the Shannon capacity of a graph. IEEE Trans. Inf. Theory,
25, 1 (1979).

[LR04]

V. Lozin and D. Rautenbach. Chordal bipartite graphs of bounded tree- and
clique-width. Discrete Math., 283, 151 (2004).

[Mad13]

A. Madry. Navigating Central Path with Electrical Flows: From Flows to
Matchings, and Back. In 2013 IEEE 54th Annu. Symp. Found. Comput. Sci.,
253–262 (2013).

[MP14]

B. D. McKay and A. Piperno. Practical graph isomorphism, II . J. Symb.
Comput., 60, 94 (2014).

[MS04]

M. Mucha and P. Sankowski. Maximum Matchings via Gaussian Elimination.
In 45th Annu. IEEE Symp. Found. Comput. Sci., 248–255 (2004).

[Pel99]

M. Pelillo. Replicator Equations, Maximal Cliques, and Graph Isomorphism.
Neural Comput., 11, 1933 (1999).

[Pon91]

I. N. Ponomarenko. The isomorphism problem for classes of graphs closed
under contraction. J. Sov. Math., 55, 1621 (1991).
28

[Pri00]

E. Prisner. Bicliques in Graphs I: Bounds on Their Number. Combinatorica,
20, 109 (2000).

[PSZ99]

M. Pelillo, K. Siddiqi and S. Zucker. Matching hierarchical structures using
association graphs. IEEE Trans. Pattern Anal. Mach. Intell., 21, 1105 (1999).

[UTN05]

R. Uehara, S. Toda and T. Nagoya. Graph isomorphism completeness for
chordal bipartite graphs and strongly chordal graphs. Discret. Appl. Math.,
145, 479 (2005).

[Wei62]

P. M. Weichsel. The Kronecker Product of Graphs. Proc. Am. Math. Soc.,
13, 47 (1962).

[ZD06]

D. Zuckerman and David. Linear degree extractors and the inapproximability
of max clique and chromatic number. In Proc. thirty-eighth Annu. ACM
Symp. Theory Comput. - STOC ’06, 681. ACM Press, New York, New York,
USA (2006).

[ZPR+ 14] Y. Zhang et al. On finding bicliques in bipartite graphs: a novel algorithm
and its application to the integration of diverse biological data types. BMC
Bioinformatics, 15, 110 (2014).

29

