Questions tagged [bipartite-graphs]
For questions about graphs for which the set of vertices can be divided into two disjoint subsets such that no edge of the graph joins two vertices from same subset.
756
questions
4
votes
0
answers
47
views
Relationship between BCH code and asymmetric Ramanujan bipartite graph ( possibility for a research collaboration)
I have been working on a research topic that deals with the binary matrices arising from the BCH codes by selecting code vectors of specific weight while discarding the rest of the code vectors that ...
- 41
5
votes
1
answer
126
views
Diving $m$ pizzas among $n$ students
I'm working on problem 4.1.14 from the book Graph Theory by Bondy and Murty. I'd appreciate a solution or hint for part 2.
Problem Statement:
$m$ identical pizzas are to be shared equally amongst $n$ ...
- 298
3
votes
0
answers
55
views
Expected number of edges to draw in a bipartite graph until you get a crossing
I was asked by a friend to calculate the number of edge crossings in a $m \times n$ complete bipartite graph:
Now play a game where you randomly select an edge with equal probability each turn: what ...
- 141
4
votes
1
answer
37
views
Problem on the cardinality of the two subsets of a bipartite graph
I am given a bipartite graph $(A \cup B, E)$ with the following property: for every $a \in A$ and $b \in B$ for which $ab \in E$, $d(a) \geq d(b)$. I must show that $ |A| \leq |B|$.
I realised that ...
1
vote
1
answer
74
views
Asymptotic upper bound on nullity of biadjacency matrix of connected bipartite graph of bounded-degree
Let $G$ be a bipartite graph with parts $V$ and $W$ of sizes $m$ and $n$, respectively. The edge-set is $E \subseteq V \times W$. The adjacency matrix of $G$ takes the form
$$
A = \begin{pmatrix}
0 &...
- 271
0
votes
0
answers
30
views
Does this polynomial enumerating subsets of edges of a bipartite graph have a name?
Let $g$ be a bipartite graph with edge set $E$ and partition $A, B$. Define the polynomial $p_g$ by
$$
p_g(x,y) = \sum_{J \subset E} (-1)^{|J|} x^{|V(J)\cap A|} y^{|V(J)\cap B|}
$$
where $V(J)$ is the ...
- 9,748
1
vote
1
answer
62
views
Is colour smoothness equivalent to finding a cover via disjoint cycles?
Let $G$ be a finite bipartite graph, with colouring function $c \colon V(G) \to \{-1, 1\}$. I want to consider the problem of finding vertex-disjoint cycles whose union spans $G$. We have the ...
- 117
0
votes
0
answers
33
views
Value range of dual variables in Jonker-Volgenant algorithm for solving linear assignment problem
In A shortest augmenting path algorithm for dense and sparse linear assignment problems an algorithm for the Linear Assignment Problem is given, with a $O(N^3)$ time complexity (where $N$ is the "...
- 171
1
vote
1
answer
43
views
Zarankiewicz’s conjecture
The Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. A few years later, Zarankiewicz published a formula that provided a solution to ...
- 525
2
votes
1
answer
60
views
Number of edges in planar bipartite graph.
Suppose G=(V,E) is a planar bipartite graph such that $V_1$ and $V_2$ are the partite sets. Suppose for all $a \in V_1$, $deg(a)\le p$ and for all $b \in V_2$, $deg(b)\le q$. If $|V_1|=x$ and $|V_2|=y$...
0
votes
1
answer
36
views
I would like to prove the following: If $C$ is an odd cycle in $G$, then $G-V(C)$ is a bipartite graph.
Let $G$ be a graph in which for every pair of odd cycles $C_1$ and $C_2$ in $G$, it holds that $V(C_1) \cap V(C_2)$ is not an empty set. I would like to prove the following: If $C$ is an odd cycle in $...
user1316777
1
vote
1
answer
43
views
A matching problem with $N$ men, $N$ women and $N$ houses [closed]
Consider a matching problem with $N$ men, $N$ women and $N$ houses where each man has to be paired with exactly $1$ woman and then each couple has to be allotted to $1$ house. Now let's consider all $...
- 113
0
votes
1
answer
53
views
$G(n,1/2)$ has a bipartite subgraph with at least $n^2/8+Cn^{3/2}$ edges
I want to show that with probability converging to $1$, $G(n,1/2)$ has a bipartite subgraph with at least $n^2/8+Cn^{3/2}$ edges for some positive constant $C$. The hint for this is to use a greedy ...
- 598
3
votes
1
answer
34
views
Hamiltonian graph on a $8\times 8$ chessboard with upper left corner and bottom right corner square removed
Suppose we are given the setup in the title. Two squares are adjacent if and only if they share a common edge. I want to find out whether the obtained graph considering squares as nodes would be ...
- 79
0
votes
0
answers
29
views
Prove that for complete biclique Ki,j that ∆(Ki,j) = χ′(Ki,j).
I am trying to prove it by contradiction.
Proof:
"Assume that ∆(Ki,j) != χ′(Ki,j) for a complete biclique (Ki,j).
If ∆(Ki,j) > χ′(Ki,j), it implies that the minimum number of colors needed to ...
