# 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.

114 questions
Filter by
Sorted by
Tagged with
31 views

### Vertex percolation on bipartite graphs

This is essentially a repost of this math overflow post since it didn't get any reception. Let $G = (V \cup C, \mathcal{E})$ be $(\gamma_V, \delta_A, \gamma_B, \delta_B)$-left-right-expanding with ...
86 views

### Given a polytope $P$ with bipartite edge-graph, if the bipartition classes are equal in size and lie on spheres, is $P$ inscribed?

Suppose that $P\subset\Bbb R^n, n\ge 3$ is a (full-dimensional) convex polytope with a bipartite edge-graph $G=(V_1\cup V_2,E)$ (for example, a zonotope). Suppose further that there are concentric ...
42 views

### Hypergraphs such that all finite subhypergraphs are bipartite

The starting point of this question is the following true statement for graphs: A simple, undirected graph $G = (V,E)$ is bipartite if and only if for all $E_0\subseteq E$ the graph $(V, E_0)$ is ...
137 views

94 views

### Volume interpretation of number of perfect matchings in bipartite planar graphs

Permanent of biadjacency of bipartite graphs is the number of perfect matchings. In the case of planar graphs we can obtain an orientation with sign changes and get away with computing the determinant ...
190 views

1 vote
625 views

### Algorithm to find a $k$-partite graph

Is there any algorithm which finds any $k$-partite graph of a given graph which is known to be a $k$-partite graph? For example, you are given a graph $G$ with vertices $V$ and edges $E$, and you ...
207 views

### Dowker and neighborhood complexes: reference wanted

Let $R$ be a 0-1 matrix whose rows or columns are maximal. Q1. Is there a name for such a matrix (or, e.g., a corresponding relation)? From 0-1 matrix corresponding to an abstract simplicial ...
667 views

### Combinatorial optimization problem for bipartite graphs

Let $G(V_1\cup V_2, E)$ be a simple bipartite graph having $n$ vertices and $m$ edges, such that $|V_1|=|V_2|$ (which implies that $n$ is an even number). Given any node $i \in V_1\cup V_2$, we denote ...
### How many $40$-vertex cubic bipartite graphs have determinant $\pm 3$?
To get some feel for the size of a particular computation, I would like to know the approximate number of (pairwise-nonisomorphic) cubic bipartite graphs on $40$ vertices whose bipartite adjacency ...
How can we prove the following conjecture? Given any simple unweighted bipartite graph $G(V_1, V_2, E)$, there always exists a subgraph $G'(V_1, V_2, E')$ of $G$ such that the two following ...