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

86 questions
Filter by
Sorted by
Tagged with
159 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 ...
87 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 ...
43 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 ...
75 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. ...
16 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$ ...
34 views

138 views

87 views

### Minimum number of edges to add in order to have a biclique cover

Given a bipartite graph G and a number N, what's the minimum number of edges I have to add to G in order to be able to cover the resulting graph with no more than N complete bipartite subgraphs? For ...
711 views

### Rank Adjacency Matrix Bipartite Graph

I am interested to know what kind of characterizations are known of the rank of bipartite graphs $G(n,m)$ ($n$ vertices on one side, $m$ on the other, $n \leq m$). When is the incidence matrix full ...
97 views

### Bipartite Defect in Graphs

This question is inspired by a recent related question. Given a bipartition $V=B \cup C$ of the vertices of a graph, call an edge $B$-monochromatic (or $C$-monochromatic) if both ends are in $B$ (or ...
83 views

### Finding large bicliques in random bipartite graph

I want to find a $k$ by $r$ biclique hidden in an $M$ by $N$ random bipartite graph where edges are present with probability $p \in [0,1]$. I am specifically interested in $p \ll 1$, and large values ...
121 views

### Matching in a bipartite graph that saturates all vertices

Let $G=(S,T;E)$ be a bipartite graph without isolated vertices. For every edge $e\in E$, e $=$ $st$ $($ s $\in S$, $t\in T$) happens the inequality $dG(s)$ $>=$ $dG(t)$. Prove that in $G$ ...
197 views

Consider a bipartite graph of order $2n$ with equal bipartitions $C_1$ and $C_2$, where, $$C_i = \{v_{i,1}, v_{i,2}, v_{i,3} \dots v_{i,n}\}; i = 1, 2.$$ Given two vertices $v_{i,p}$ and $v_{i,q}$, $... 2answers 738 views ### Maximum number of edges in bipartite graph without cycles of length 4 Let$ex(n,H)$denote the maximum number of edges of a graph on$n$vertices not containing a copy of$H$. Let$ex(n,m,H)$denote the maximum number of edges of a bipartite graph with parts' sizes$m$... 1answer 432 views ### Minimum modifications to make a graph bipartite Let's say I have a graph that is not bipartite. Let's say it is colored red and black and there are some conflicts where two vertices of the same color share an edge. I can introduce a new vertex ... 0answers 329 views ### Missing count in number of perfect matchings Let$f(G)$give number of perfect matchings of a graph$G$. Denote$\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Denote collection of all$2n$vertex balanced bipartite graph to be$\mathcal G_{2n}$. ... 1answer 190 views ### What is the densest bipartite graph with unique Hamiltonian cycle? In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than$n^2$edges, if graph has$2n$vertices. Analogously, what is the ... 0answers 108 views ### Maximum number of$4$-cycles Suppose we have a balanced bipartite planar maximum degree$k$graph. How many such graphs on$2n$vertices have at most$f(n)$maximum number of$4$cycles for a given function$f:\Bbb R^+\...
What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$? I am most interested in $d\leq3$ and $g=0$.