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.
0
votes
0answers
5 views
Bipartite Graph [migrated]
Is there a bipartite graph with the following degrees: 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 6, 6?
I've tried so many different combinations and I don't think there is a way to make a bipartite graph this ...
6
votes
1answer
142 views
Does high min degree and high odd girth imply near bipartiteness?
Say $G$ has odd girth at least $k$ and min degree $2n/k$. There is a classical result by Andrasfai, Erdos, and Sos that says that $G$ is bipartite. (Odd girth is the length of the shortest odd cycle ...
1
vote
0answers
95 views
Bipartite independence number
Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.
The bipartite independence number of ...
1
vote
2answers
325 views
Enumeration of labeled connected bipartite graphs given partite sets
What would be the closed-form expression defining number of all possible labelled connected bipartite graphs given $\mid X \mid = m, \mid Y \mid = n - m $?
1
vote
0answers
56 views
Details about Kelman's equivalent form of Barnette's conjecture
Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles.
Kelman claims that this conjecture is equivalent to a stronger one, which imposes some ...
2
votes
1answer
260 views
bipartite graph coloring
Hi, I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is a bipartite graph G with the two vertex sets V1, V2. Each ...
0
votes
1answer
162 views
Counting matchings in a bipartite matching-covered graph
A graph is called matching-covered if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by Lovasz & ...
2
votes
1answer
120 views
Searching for equal subsets in a bipartite graph
Let $(U,V)$ be a finite bipartite graph of two parts $U$ and $V$. For any subset $u\subset U$ define the image $Im(u)$ in $V$ consisting of all vertices of $V$ connected to at least one vertex of $u$.
...
0
votes
1answer
152 views
Good lower bound on matching in bipartite graph
Suppose a bipartite graph $G=(V_1 \cup V_2, E)$ is given, and one is interested in matching vertices $V_1$ to vertices $V_2$. Assume Hall's condition does not hold, so a perfect matching does not ...
4
votes
2answers
151 views
Bipartiteness criterion
A graph is bipartite if and only if it does not contain odd cycles. Is there a similar criterion for hypergraphs? (A hypergraph is called bipartite if its vertices can be colored in two colors so that ...
2
votes
0answers
122 views
Structure of almost all bipartite graphs
I am studying some properties related to bipartite graphs and it would be useful for me to know if there is anything known about the structure of almost all bipartite graphs. For example, is it true ...
1
vote
2answers
281 views
Similarity measure between 2 bi-partite graph.
Hello there, i need to solve this problem:
I have 2 different bi-partite weighted graph, g1 and g2 and i would like to measure their similarity, g1 and g2 may have different number of vertex and edges ...
1
vote
0answers
89 views
How many extreme maximal cliques are in an n*m 0-1 matrix?
We can use an n*m 0-1 matrix to denote a bipartite graph. Mining maximal bicliques in such matrix is an open problem.
The extreme maximal clique is a special maximal clique. A clique in such matrix ...
8
votes
1answer
340 views
When does a `distinguished matching' exist?
Suppose I have a bipartite graph on a pair of vertex sets $X$ and $Y$.
Definition: A distinguished matching is a subset $DX\subseteq X$ and a subset $DY\subseteq Y$ such that:
For all $y\in Y$, ...
2
votes
2answers
148 views
Finding maximal k-degenerate subgraphs
Given a graph $G$, let $H$ be a $k$-degenerate (not necessarily induced) subgraph of maximal size. Are there any known lower bounds on $|E(H)|$ for particular classes of $G$ and values of $k$?
I've ...
4
votes
0answers
142 views
Bounds on numbers of matchings of given sizes in bipartite graphs
I am interested in the following question:
For which sets ${m_1,\ldots m_k}$ of positive integers do there exist bipartite graphs having exactly $m_i$ matchings of size $i$ for each $1\leq i \leq k$, ...
9
votes
2answers
465 views
Gale-Ryser stable marriage theorem: can we entrust matchmaking to monkeys?
Disclaimer: This is a question I have not done any real research about. I asked it myself some 5 years ago, and back then I had no idea where to start. Now I have some texts on stable matchings lying ...
2
votes
1answer
221 views
Bipartite graphs with prescribed Matching $M$ and genus $g$.
Let $B_{n,n}$ be a bipartite graph on $2n$ vertices with $n$ vertices of each color.
Given two integers $g$ and $M$, construct the smallest genus $g$ $B_{n,n}$ with exactly $M$ matchings.
My first ...
6
votes
2answers
601 views
Condition on a bipartite graph to have an $m$-factor
This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago.
Let $G$ be a bipartite graph, i. e., a graph ...
