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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
user avatar
  • 1
4 votes
1 answer
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 ...
user avatar
  • 9,887
0 votes
1 answer
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 ...
user avatar
3 votes
0 answers
137 views

Independent sets with few neighbours

[Posted this first at math stackexchange, but it probably fits better here.] I am looking for references about the following problem. Given a (connected) bipartite graph $G$, find an independent set $...
user avatar
  • 328
1 vote
1 answer
104 views

Discrepancy of random bipartite graphs (2)

This question is a modification of the one asked here, which turned out to ask for something too strong to be true. Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ ...
user avatar
3 votes
1 answer
134 views

Discrepancy of random bipartite graphs

This is a crosspost from MathStackExchange (original question). Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$). Define a ...
user avatar
-1 votes
1 answer
97 views

Are all subdivisions of bipartite graphs also bipartite?

Excuse the poor quality image, but it illustrates my point well enough. I couldn't find the answer anywhere else online.
user avatar
0 votes
1 answer
111 views

Best algorithm for meeting scheduling optimization so that total number of held meetings is minimized

Problem Description I want to hold meetings where some given number of people will participate. They have some vacant dates respectively but they don't have the same date on which all of them can ...
user avatar
1 vote
1 answer
79 views

$K_{k,m}$ is $k$-choosable if and only if $m<k^k$

This statement is proved by Vizing and Erdos & Rubin (page 30) independently. But I cannot find Vizing's paper (It's too old) and Erdos & Rubin's paper only says 'It is easily proved'. I ...
user avatar
  • 321
2 votes
1 answer
234 views

Connectivity and the minimum degree of bipartite graph

I want to find a condition on $\delta(G)$ (ex. $\delta(G) \geq an$) that guarantees $\kappa(G)=\delta(G)$ where $\kappa(G)$ is the vertex-connectivity of a bipartite graph $G$, and $\delta(G)$ is the ...
user avatar
  • 321
2 votes
0 answers
56 views

Sum of number of perfect matchings and a constant constuction

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
user avatar
  • 13k
8 votes
0 answers
229 views

Sum of perfect matching construction

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
user avatar
  • 13k
1 vote
1 answer
97 views

Succinct polynomial sized representation of balanced bipartite graphs whose perfect matching count is a primorial

Is there a $P$ time definable sequence of succinct polynomial sized representation of balanced bipartite graphs whose number of perfect matchings is a primorial? For factorial a complete bipartite ...
user avatar
  • 13k
5 votes
1 answer
241 views

Bipartite graph with exactly one perfect matching

$\textbf{Problem:}$ Find all bipartite graphs $G[X,Y]$ satisfying the following properties: $1.$ $|X|=|Y|$, where $|X|\ge 2$ and $|Y|\ge 2$. $2.$ All vertices have degree three except for two vertices ...
user avatar
3 votes
1 answer
400 views

The number of elements in {1,2,...,a}.{1,2,...,b}, where $ab=n^2$

Let $A_{a,b}$=$\{pq:p\leq a,q\leq b\}$, where $ab=n^2$ and $n^2$ is fixed. How large is $A_{a,b}$? Does $A_{a,b}$ attain its lower value when $a=b=n$? The case when $a=b=n$ is settled by Ford, and a ...
user avatar
  • 139
2 votes
1 answer
185 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 ...
user avatar
6 votes
1 answer
207 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 ...
user avatar
2 votes
0 answers
43 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 ...
user avatar
  • 241
1 vote
0 answers
73 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 ...
user avatar
  • 13k
1 vote
1 answer
182 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'}$ ...
user avatar
  • 13k
1 vote
0 answers
77 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$...
user avatar
  • 13k
1 vote
0 answers
108 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 ...
user avatar
  • 1,701
2 votes
1 answer
137 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 ...
user avatar
2 votes
0 answers
63 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 ...
user avatar
  • 21
5 votes
2 answers
313 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....
user avatar
  • 125
1 vote
2 answers
375 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 ...
user avatar
1 vote
0 answers
28 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 ...
user avatar
  • 11.1k
6 votes
0 answers
243 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 ...
user avatar
1 vote
2 answers
91 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 ...
user avatar
4 votes
0 answers
63 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 ...
user avatar
  • 9,887
2 votes
2 answers
118 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. ...
user avatar
  • 31
1 vote
0 answers
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$ ...
user avatar
2 votes
0 answers
77 views

How many edges can be in an unbalanced bipartite graph of girth $>6$?

Let $G = (V, E)$ be a bipartite graph with $n, m$ nodes in its bipartition and girth (shortest cycle length) $>6$. There is a simple counting argument called the Moore Bounds that gives $$|E| = O\...
user avatar
  • 1,349
1 vote
0 answers
67 views

Treewidth related properties of a bipartite graph with bounded local crossing number and diameter

If a bipartite degree at most $3$ graph on $O(n^2)$ vertices with diameter at most $O(\log n)$ has property that every edge intersects at most $O(\log n)$ edges on a planar drawing then does any of ...
user avatar
  • 1,728
3 votes
1 answer
116 views

Partitioning vertex set to maximize weights of inter-class edges?

An interesting problem has come up in my work, and I haven't quite been able to find references to it so I thought I'd ask here. Suppose we have some complete, weighted graph with vertex set $V$. Is ...
user avatar
1 vote
1 answer
79 views

Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph

What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am ...
user avatar
  • 13k
2 votes
0 answers
73 views

Statistics of perfect matching and incremental perfect matchings in bipartite planar graphs?

Planar graph permanent can be reduced to determinants and so statistics should be amenable. Pick a uniformly random bipartite planar graph $G$ with $n$ vertices of each color and choose new additional ...
user avatar
  • 13k
3 votes
1 answer
323 views

Minimum planar bipartite graph to cover all perfect matching count

Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
user avatar
  • 13k
4 votes
0 answers
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 ...
user avatar
  • 13k
5 votes
1 answer
190 views

"König's theorem" for $T_2$-spaces?

For any topological space $(X,\tau)$ we define a matching to be a collection of non-empty and pairwise disjoint open sets. We define the matching number $\nu(X,\tau)$ to be the smallest cardinal $\...
user avatar
3 votes
0 answers
89 views

Have partition functions of abstract simplicial complexes been examined?

Many complicated probability distributions arising in electrical engineering and machine learning have a simple expression as a sum of products that can also be encoded in a factor graph. The ...
user avatar
1 vote
1 answer
129 views

An variation of an assignment problem in combinatorics: assign items to customers

Suppose we want to assign $n$ items to $m$ customers ($n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. ...
user avatar
-1 votes
2 answers
73 views

On a condition concerning the number of neighbors in bipartite graphs

For any undirected simple graph $G=(V,E)$ we define for $v\in V$ the set $N(v) = \{w\in V: \{v,w\}\in E\}$. Suppose $A, B$ are finite, disjoint sets, and $G = (A\cup B, E)$ is a bipartite graph with ...
user avatar
1 vote
0 answers
133 views

Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard. Is it? Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...
user avatar
0 votes
1 answer
107 views

Maximum partition of bipartite graph

Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 111
6 votes
0 answers
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 ...
user avatar
6 votes
1 answer
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 ...
user avatar
5 votes
3 answers
215 views

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 ...
user avatar
  • 10.8k
2 votes
1 answer
166 views

Existence of bipartite subgraphs satisfying degree and edge cardinality constraints

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 ...
user avatar