# Questions tagged [bipartite-graphs]

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices in the same set are adjacent.

97 questions
Filter by
Sorted by
Tagged with
1answer
134 views

### At most one perfect matching of a bipartite graph

I. Given biadjacency matrix $A$ of a bipartite graph on $2n$ vertices having $n$ vertices of either color on the constraints the graph either has $0$ perfect matchings $1$ perfect matchings is it ...
1answer
140 views

### Can we construct a dessin of any genus with a cyclic automorphism group of any order?

We consider a dessin d'enfant $D$ as a bipartite graph $D$ on a complex oriented surface $S$, such that the complement $S \backslash D$ is homotopic to a collection of disks. Definition: Let an ...
0answers
28 views

### Computing bipartite matching of size $k$?

Given a bipartite graph with $n$ vertices on each side and an integer $k$, how can we compute all bipartite matchings of size $k$? The problem of computing all perfect matchings is #P-complete. But I ...
0answers
67 views

### Number of extremal $\{0,1\}$ matrices having permanent $1$ property

Is there a function which describes the number of $\{0,1\}^{n\times n}\cap\mathbb Z^{n\times n}$ matrices having permanent $1$? I think it might be $\mathsf{poly}(n!)$ bounded. Is there a function ...
1answer
79 views

### Unique bipartite perfect matchings and cycles?

Given a graph $G$ which is bipartite and balanced and has unique perfect matching let $G^{e}$ be $G$ without edge $e$. Let $G\cup G_{\pi,\pi'}$ be union of $G$ and $G_{\pi,\pi'}$ where $G_{\pi,\pi'}$ ...
0answers
65 views

### Is there a bipartite graph whose determinant corresponds to number of perfect matchings?

Let $M\in\{0,1\}^{n\times n}$ be a square integer matrix. If we consider $M$ as biadjacency of a balanced bipartite graph on $2n$ vertices having $n$ vertices of color $1$ and $n$ vertices of color $2$...
0answers
94 views

### A query on Galvin's theorem for bipartite graphs

The Galvin's theorem is the generalized version of Dinitz conjecture that states that if the maximum degree of any bipartite graph is $\Delta$, then its edges are colorable properly if each of its ...
0answers
98 views

### Two from cubic subgraph hardness

The Problem For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3. The cubic subgraph problem is NP-hard even in bipartite planar graphs with ...
0answers
43 views

### Counting the number of simple labelled bipartite graphs 𝐺𝑛,𝑚 with 𝑘 edges such that 𝑑1 vertices have degree 1

I have tried to count the number of simple labelled bipartite graphs $G_{n,m}$ with $k$ edges such that $d_1$ vertices have degree 1. Has this problem been studied? So far the only related paper I ...
2answers
278 views

### Conjecture about minimal number of edge crossings in complete bipartite graphs

I am interested in the status of the conjecture about the minimum number of edge crossings $cr(K_{m,n})$ in a drawing of the complete bipartite graph $K_{m,n}$. The Wikipedia article https://en....
2answers
210 views

### What is a bipartite hypergraph?

Bipartite graphs are very useful, and I am looking for a generalization of this concept to hypergraphs. I found two different definitions of bipartite hypergraphs: In the Wikipedia page Hypergraph, a ...
0answers
24 views

### Optimal preprocessing in the Kuhn-Munkres algorithm

The matrix formulation of the Kuhn-Munkres algorithm for solving the Linear Assignment Problem requires a preprocessing in which the minimal values of a line be subtracted from every value in that ...
0answers
216 views

### Probability that a random multigraph is simple

Question. Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...
2answers
90 views

### One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets s.t. just a fraction of first part see all 3 subsets

Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$. Now, is it possible to color vertices in $U$ with 3 colors ...
0answers
56 views

### If all 2-faces of a polytope are $2n$-gons, is the edge-graph bipartite?

This question on MSE has not received a satisfying answer. It can be summarized as follows: Question: Is is true that the edge-graph of a (convex) polytope is bipartite if and only if all 2-faces ...
2answers
85 views

### Number of subgraphs with matching of size $n$ for a complete bipartite graph

Say we have a $K_{n,n}$ bipartite graph (i.e. a complete bipartite graph with $n$ nodes on each side). We induce a subgraph by deleting some subset of edges. There are $2^{n^2}$ possible subgraphs. ...
0answers
19 views

### Hadwiger number in vertex collapse in a bipartite graph

If $G=(V,E)$ is a finite graph, let the Hadwiger number $\eta(G)$ equal the largest integer $n$ such that the complete graph $K_n$ is a minor of $G$. Is there a bipartite graph $G$ on more than $3$ ...
0answers
47 views

0answers
141 views

1answer
89 views

### Minimum number of edges to add in order to have a biclique cover

Given a bipartite graph G and a number N, what's the minimum number of edges I have to add to G in order to be able to cover the resulting graph with no more than N complete bipartite subgraphs? For ...
2answers
886 views

### Rank adjacency matrix bipartite graph

I am interested to know what kind of characterizations are known of the rank of bipartite graphs $G(n,m)$ ($n$ vertices on one side, $m$ on the other, $n \leq m$). When is the incidence matrix full ...