1
vote
1answer
123 views

Sequences that represent different drawing of chords?

In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties. Actually my question is ...
6
votes
1answer
143 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
99 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
357 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 $?
0
votes
1answer
212 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 & ...
4
votes
2answers
153 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
128 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 ...
8
votes
1answer
344 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
176 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 ...
9
votes
2answers
469 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
312 views

Obstructions to genus $g+1$ bipartite graph having genus $g$

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with each color assigned to $n$ vertices. Say I know $g \le \operatorname{genus}(B_{n,n}) \le g+1$. What obstructions prevent $B_{n,n}$ from being ...