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

648 questions
Filter by
Sorted by
Tagged with
1 vote
52 views

### Discrepancy of random bipartite graphs

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 random bipartite graph on $X \sqcup Y$ in an Erdos-Renyi fashion ...
26 views

### Are the following two properties of Eulerian graphs true?

Can someone help to verify the following two properties, perhaps by indicating what properties of eulerian graphs is used in them? Q1: Let $G$ be a connected graph containing a Eulerian circuit. If $G$...
24 views

### Is this an incorrect application of Tutte's theorem of perfect matching for bipartite graphs?

This is an extract from a conference paper. It seems the authors are invoking Tutte's theorem (since  refers to the 1947 paper) to conclude that a matrix $J(x)$ with given numerical entries is ...
1 vote
23 views

### Tutte's matrix for perfect matching in bipartite graphs

I came across Tutte's matrix for a bipartite graph $G(U, V, E)$ in two different forms. One form (seen in these notes for example https://www.cs.cmu.edu/afs/cs/academic/class/15859-f04/www/scribes/...
1 vote
31 views

### Finding 2 edge disjoint perfect matching in a bipartite graph

Is it NP-hard to decide if an arbitrary bipartite graph has 2 edge disjoint perfect matchings? It is hard for cubic graphs, but I am not sure whether it is still hard for bipartite graphs.
45 views

### Stable marriage problem with all men having the same preference (2)

I saw this problem today: Stable marriage problem with all men having the same preference After look at this problem, I have a feeling that if one side shares the same exact preference, there will ...
25 views

### Constrained coloring of bigraph nodes

I have a graph $G(U,V,E)$ representing a set of documents ($U$) and queries ($V$). Every document has 1-5 queries it is connected to, and every query has 1-50 documents it is connected to. There are ~...
26 views

### Finding a binary vector that satisfies non-linear constraints

I’m looking for good heuristics for finding at least one (of a probably large set, although possibly none) high dimensional ($|v|>5000$) binary vector that satisfies a set of non-linear/non-...
46 views

### A question on bipartite graph

So I've been asked to find how many vertices are there on $G$. $G$ is a bipartite graph of order $n$ partitioned to $A$ and $B$ where $A$ has an order of $10$ which every vertex in $A$ has degree $6$. ...
36 views

### Maximum "k-to-k" matching in bipartite graph

I was "inspired" to extend the concept of Maximum "$2$-to-$1$" matching in a bipartite graph 2-to-1 matching by extending it to "k-to-k" matching for some natural number ...
24 views

### Calculation of cost of all possible perfect matchings in bipartite graph.

I have A Bipartite Graph $G(U,V,E)$ with positive costs on the edges, $|U|=|V|=n$. Is there an efficient way to calculate the cumulative cost of all possible perfect matchings $\sum_{m\in M}C(m)$ ...
26 views

### Difference between the definitions of connected and bipartite graphs

The question which I am about to ask is closely related with this one. Question: In the definition of bipartite graphs we consider partitions $X, Y$ to be any subset of $V$. If we require them to be ...
74 views

### Definition of bipartite graph from Murty-Bondy book

I was reading reading the definition of bipartite graph and one moment is confusing me. Due to this definition we can consider any graph $G=(V,E)$ as a bipartite, if we take $X=\varnothing$ and $Y=V$. ...
26 views

### Proposition about cardinality of partitions of bipartite graph

I was reading "Graph Theory" by Murty and Bondy and came across the following theorem which confuses me a bit. In the line which I've highlighted by red color it seems that they are using ...
38 views

### Proving that an edge is not an element of a matching.

Let $G$ be bipartite such that $G=(Y,E)$. Let $W \subset Y$ be a minimum vertex cover in $G$ and let $M \subset E$ be a maximum matching in bipartite graph $G$. Prove that for any edge $wy \in E$, if ...
19 views

### Difference between biregular and regular bipartite graph

According to wikipedia biregular graphs have two independent set each containing vertices of same degree. So, any vertex can have either of the two degrees (based upon the independent set they belong ...
1 vote
121 views

1 vote
76 views

### Graph coloring where a maximum of 2 neighboring nodes can have the same color.

We are given a graph where each node can have at most 3 edges. We want to color this graph into 2 colors such that each node can have at most one neighbor with the same color as itself. How to prove ...
1 vote
48 views

### Hungarian algorithm / assignment problem with cost function depending on resultant matching

The standard Hungarian algorithm solves the problem of assigning n workers to n jobs with a given cost function. In my variant, the cost function depends on the final matching produced by the ...
### Existence of a path of length $n/2$ in every bipartite graph with $d(A,B)=1/2$.
Claim: Let $G=A\cup B$ be a balanced bipartite graph with $e(A,B) \geq n/2$ then $G$ has a path of length $n/2$. I know about the erdos-gallai theorem that would net a path of length $n/4$. By noting ...