# 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
Filter by
Sorted by
Tagged with
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
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
221 views

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