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.
128
questions
0
votes
0
answers
9
views
Existence of adjacent $a, b$ in a general bipartite graph (with a special degree condition) such that $\frac{deg(a)}{deg(b)} \ge \frac{|B|}{|A|}$
Suppose a bipartite graph with two parts $A, B$, for every ${b \in B}$ we know $deg(b) \ge 1$.
Prove there exists an adjacent $a \in A, b \in B$ such that $\frac{deg(a)}{deg(b)} \ge \frac{|B|}{|A|}$.
- 127
2
votes
0
answers
115
views
Generalizing Hall's marriage theorem to non-perfect matchings
Let $G = (X, Y, E)$ be bipartite graph such that $|X|=|Y|=n$.
A matching $M \subseteq E$ is a subset of disjoint edges
(i.e., there does not exist a pair of edges $(x, y) \in M$ and $(x', y') \in M$ ...
- 121
3
votes
1
answer
221
views
Are "ultra-regular" bipartite graphs complete?
Let $X, Y$ be non-empty, disjoint sets and let $R\subseteq X\times Y$ be a binary relation. For $x\in X$, we set $R(x) = \{y\in Y: (x,y) \in R\}$ and for $y\in Y$, let $R^{-1}(y) = \{x\in X:(x,y)\in R\...
- 44.4k
1
vote
0
answers
30
views
Tightness of the bounding the operator norm of graph by average degree from below
Let $G = (V,E)$ be a simple graph with adjacency matrix $A$. It is well known that the largest eigenvalue
$\lambda_{1}$ of $A$ is contained within the interval $[d, D]$ where $d$ is the average degree ...
- 381
15
votes
1
answer
1k
views
Parity and the Axiom of Choice
Motivation. The three-dimensional cube can be formalized by $\mathcal P(\{0,1,2\})$ where vertices $x,y\in\mathcal P(\{0,1,2\})$ are connected by an edge if and only if their symmetric difference $x\...
- 44.4k
0
votes
1
answer
48
views
Real-world datasets for testing the maximum edge bi-clique problem
We have proposed a new approach to solve the maximum edge bi-clique problem, however, we couldn't succeed to find real-world datasets (graph or bipartite graph datasets) to test our approach. Does ...
3
votes
0
answers
86
views
Number of planar bipartite graphs
How many planar bipartite graphs are there with $m$ vertices of one color and $n$ vertices of the other color?
How many non-isomorphic classes exist?
- 13.5k
2
votes
0
answers
147
views
Ramanujan graphs in Polynomial time
I am a research scholar with a computer science background, currently working on graph theory. I am working on a reduction to prove that a problem is NP-complete. I need to include the Ramanujan graph ...
0
votes
0
answers
28
views
Finding a bipartite graph that contains a specific elements of perfect matchings
I am a physicist who is interested in the applications of graph theory.
I've been studying the bipartite graphs and perfect matching finding problems. I see there are several research works on ...
3
votes
1
answer
143
views
For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours
Given a partition of the edges of $K_{n,n}$ into $n$ colours, where each colour appears exactly $n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
0
votes
1
answer
107
views
Entropy of eigenvectors of (traceless) laplacian of a bipartite graph
This problem is motivated by the edge states that sometimes appear (and sometimes not) at the level of Huckel hamiltonians for $\pi$-conjugated benzenoid hydrocarbons. If this sentence is cryptic, ...
- 251
1
vote
0
answers
70
views
Concavity of expected size of a maximum matching (in a bipartite graph) w.r.t. edge probability
Given a n*n bipartite graph where each edge (between any two nodes on the opposite side) is formed i.i.d. with probability $p$, can we show a concavity result on the expected size of a maximum ...
- 53
3
votes
1
answer
129
views
"Geodesic coherent" partition of a graph
Let $G=(V,E)$ be a finite undirected graph which we equip with its usual graph geodesic distance $d_G$ making $(G,d_G)$ into a metric space; let $1<\#V<\infty$. For a given $1<N< \#V$ ...
- 5,001
8
votes
0
answers
111
views
Conceptual explanation for the gap in the spectrum of biregular trees
Ramanujan graphs are defined as $(q+1)$-regular graphs for which all nontrivial eigenvalues of the adjacency operator are contained in the interval
$$[-2\sqrt{q}, 2\sqrt{q}].$$
The reason for this ...
- 2,775
2
votes
1
answer
106
views
Minimal cardinality of non-bipartite sub-family of $[\omega]^\omega$
Let $[\omega]^\omega$ the collection of infinite subsets of $\omega$. We say that $E\subseteq [\omega]^\omega$ is bipartite if there is $d\subseteq \omega$ such that for all $e\in E$ the intersections ...
- 44.4k
4
votes
1
answer
108
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 ...
- 11.9k
0
votes
1
answer
53
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 ...
- 44.4k
4
votes
0
answers
150
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 $...
- 338
1
vote
1
answer
134
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$ ...
- 2,775
3
votes
1
answer
175
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 ...
- 2,775
-1
votes
1
answer
219
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.
0
votes
1
answer
452
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 ...
- 11
1
vote
1
answer
144
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 ...
- 331
2
votes
1
answer
451
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 ...
- 331
2
votes
0
answers
60
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 ...
- 13.5k
8
votes
0
answers
241
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 ...
- 13.5k
1
vote
1
answer
109
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 ...
- 13.5k
5
votes
1
answer
608
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 ...
- 181
3
votes
1
answer
411
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 ...
- 139
2
votes
1
answer
312
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 ...
- 23
6
votes
1
answer
232
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 ...
- 3,509
2
votes
0
answers
73
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 ...
- 241
1
vote
0
answers
91
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 ...
- 13.5k
1
vote
1
answer
255
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'}$ ...
- 13.5k
1
vote
0
answers
103
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$...
- 13.5k
1
vote
0
answers
152
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 ...
- 1,841
2
votes
1
answer
172
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 ...
2
votes
0
answers
96
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 ...
- 21
5
votes
2
answers
357
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....
- 125
1
vote
2
answers
598
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 ...
- 3,525
1
vote
0
answers
43
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 ...
- 12.4k
6
votes
0
answers
264
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 ...
- 1,365
1
vote
2
answers
93
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 ...
4
votes
0
answers
73
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 ...
- 11.9k
2
votes
2
answers
182
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. ...
- 31
1
vote
0
answers
24
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$ ...
- 44.4k
2
votes
0
answers
128
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\...
- 1,379
1
vote
0
answers
101
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 ...
- 1,796
3
votes
1
answer
256
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 ...
1
vote
1
answer
88
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 ...
- 13.5k