# All Questions

Tagged with graph-theory bipartite-graphs

63
questions

**1**

vote

**0**answers

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

**3**

votes

**1**answer

47 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

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

**5**

votes

**1**answer

164 views

### “König's theorem” for $T_2$-spaces?

For any topological space $(X,\tau)$ we define a matching to be a collection of non-empty and pairwise disjoint open sets. We define the matching number $\nu(X,\tau)$ to be the smallest cardinal $\...

**-1**

votes

**2**answers

70 views

### On a condition concerning the number of neighbors in bipartite graphs

For any undirected simple graph $G=(V,E)$ we define for $v\in V$ the set $N(v) = \{w\in V: \{v,w\}\in E\}$.
Suppose $A, B$ are finite, disjoint sets, and $G = (A\cup B, E)$ is a bipartite graph with ...

**1**

vote

**0**answers

116 views

### Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard. Is it?
Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...

**0**

votes

**1**answer

87 views

### Maximum partition of bipartite graph

Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\...

**1**

vote

**1**answer

249 views

### Algorithm to find a $k$-partite graph

Is there any algorithm which finds any $k$-partite graph of a given graph which is known to be a $k$-partite graph?
For example, you are given a graph $G$ with vertices $V$ and edges $E$, and you ...

**4**

votes

**1**answer

443 views

### Combinatorial optimization problem for bipartite graphs

Let $G(V_1\cup V_2, E)$ be a simple bipartite graph having $n$ vertices and $m$ edges, such that $|V_1|=|V_2|$ (which implies that $n$ is an even number). Given any node $i \in V_1\cup V_2$, we denote ...

**5**

votes

**3**answers

171 views

### How many $40$-vertex cubic bipartite graphs have determinant $\pm 3$?

To get some feel for the size of a particular computation, I would like to know the approximate number of (pairwise-nonisomorphic) cubic bipartite graphs on $40$ vertices whose bipartite adjacency ...

**2**

votes

**1**answer

104 views

### Existence of bipartite subgraphs satisfying degree and edge cardinality constraints

How can we prove the following conjecture?
Given any simple unweighted bipartite graph $G(V_1, V_2, E)$, there always exists a subgraph $G'(V_1, V_2, E')$ of $G$ such that the two following ...

**1**

vote

**2**answers

167 views

### Hamiltonicity and minimal degree in bipartite graphs

Given an integer $k>1$, is there a connected bipartite graph $\Gamma = (A, B, E)$ where $A\cap B = \emptyset$ and $E \subseteq \big\{\{a, b\}:a\in A, b\in B\big\}$ such that
$|A| = |B|$,
$\text{...

**1**

vote

**3**answers

297 views

### Hamiltonian paths in bipartite graphs with 2 sets of “almost” same cardinality

Suppose we have two finite disjoint sets $A, B \neq \emptyset$ such that $|A|$ and $|B|$ differ by at most $1$, and let $\Gamma = (A\cup B, E)$ where $E\subseteq \big\{\{a,b\}: a\in A, b\in B\big\}$ ...

**7**

votes

**1**answer

370 views

### Graph to Bipartite conversion preserving number of perfect matchings

Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that ...

**2**

votes

**0**answers

142 views

### Minimal size of the maximum biclique

We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each vertex on side $R$ is connected to $k$ vertices on side $...