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 L …

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 set …

Prove or Disprove: A k-regular bipartite graph (a bipartite graph where every vertex has degree k) has at least k! perfect matchings.

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 leas …

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 …

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 ma …

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: …

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 i …

Suppose a bipartite graph $G=(V_1 \cup V_2,E)$ is given, and a weight $w_e \geq 0$ is associated with each edge $e \in E$. The interest is to match vertices $V_1$ to vertices $V_2$ …

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 e …

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 cli …

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 v …

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 gr …

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 sta …

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 ea …