Questions tagged [bipartite-graphs]

For questions about graphs for which the set of vertices can be divided into two disjoint subsets such that no edge of the graph joins two vertices from same subset.

Filter by
Sorted by
Tagged with
1 vote
0 answers
52 views

Discrepancy of random bipartite graphs

Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$). Define a random bipartite graph on $X \sqcup Y$ in an Erdos-Renyi fashion ...
user avatar
0 votes
1 answer
26 views

Are the following two properties of Eulerian graphs true?

Can someone help to verify the following two properties, perhaps by indicating what properties of eulerian graphs is used in them? Q1: Let $G$ be a connected graph containing a Eulerian circuit. If $G$...
user avatar
0 votes
0 answers
24 views

Is this an incorrect application of Tutte's theorem of perfect matching for bipartite graphs?

This is an extract from a conference paper. It seems the authors are invoking Tutte's theorem (since [12] refers to the 1947 paper) to conclude that a matrix $J(x)$ with given numerical entries is ...
user avatar
  • 1,043
1 vote
1 answer
23 views

Tutte's matrix for perfect matching in bipartite graphs

I came across Tutte's matrix for a bipartite graph $G(U, V, E)$ in two different forms. One form (seen in these notes for example https://www.cs.cmu.edu/afs/cs/academic/class/15859-f04/www/scribes/...
user avatar
  • 1,043
1 vote
1 answer
31 views

Finding 2 edge disjoint perfect matching in a bipartite graph

Is it NP-hard to decide if an arbitrary bipartite graph has 2 edge disjoint perfect matchings? It is hard for cubic graphs, but I am not sure whether it is still hard for bipartite graphs.
user avatar
  • 43
2 votes
1 answer
45 views

Stable marriage problem with all men having the same preference (2)

I saw this problem today: Stable marriage problem with all men having the same preference After look at this problem, I have a feeling that if one side shares the same exact preference, there will ...
user avatar
0 votes
0 answers
25 views

Constrained coloring of bigraph nodes

I have a graph $G(U,V,E)$ representing a set of documents ($U$) and queries ($V$). Every document has 1-5 queries it is connected to, and every query has 1-50 documents it is connected to. There are ~...
user avatar
  • 176
0 votes
0 answers
26 views

Finding a binary vector that satisfies non-linear constraints

I’m looking for good heuristics for finding at least one (of a probably large set, although possibly none) high dimensional ($|v|>5000$) binary vector that satisfies a set of non-linear/non-...
user avatar
  • 176
0 votes
2 answers
46 views

A question on bipartite graph

So I've been asked to find how many vertices are there on $G$. $G$ is a bipartite graph of order $n$ partitioned to $A$ and $B$ where $A$ has an order of $10$ which every vertex in $A$ has degree $6$. ...
user avatar
0 votes
1 answer
36 views

Maximum "k-to-k" matching in bipartite graph

I was "inspired" to extend the concept of Maximum "$2$-to-$1$" matching in a bipartite graph 2-to-1 matching by extending it to "k-to-k" matching for some natural number ...
user avatar
  • 33
0 votes
0 answers
24 views

Calculation of cost of all possible perfect matchings in bipartite graph.

I have A Bipartite Graph $G(U,V,E)$ with positive costs on the edges, $|U|=|V|=n$. Is there an efficient way to calculate the cumulative cost of all possible perfect matchings $\sum_{m\in M}C(m)$ ...
user avatar
  • 43
0 votes
1 answer
26 views

Difference between the definitions of connected and bipartite graphs

The question which I am about to ask is closely related with this one. Question: In the definition of bipartite graphs we consider partitions $X, Y$ to be any subset of $V$. If we require them to be ...
user avatar
  • 14.7k
3 votes
2 answers
74 views

Definition of bipartite graph from Murty-Bondy book

I was reading reading the definition of bipartite graph and one moment is confusing me. Due to this definition we can consider any graph $G=(V,E)$ as a bipartite, if we take $X=\varnothing$ and $Y=V$. ...
user avatar
  • 14.7k
0 votes
1 answer
26 views

Proposition about cardinality of partitions of bipartite graph

I was reading "Graph Theory" by Murty and Bondy and came across the following theorem which confuses me a bit. In the line which I've highlighted by red color it seems that they are using ...
user avatar
  • 14.7k
0 votes
1 answer
38 views

Proving that an edge is not an element of a matching.

Let $G$ be bipartite such that $G=(Y,E)$. Let $W \subset Y$ be a minimum vertex cover in $G$ and let $M \subset E$ be a maximum matching in bipartite graph $G$. Prove that for any edge $wy \in E$, if ...
user avatar
  • 9
0 votes
0 answers
19 views

Difference between biregular and regular bipartite graph

According to wikipedia biregular graphs have two independent set each containing vertices of same degree. So, any vertex can have either of the two degrees (based upon the independent set they belong ...
user avatar
  • 2,239
1 vote
0 answers
121 views

Estimate $\sum_{x\in\mathbb{F}_q}\deg(x)(\deg(x)-1)$ in the bipartite graph with no 4-cycles

Consider a finite field $\mathbb{F}_q$ and polynomials $g(x),h(x)$ over $\mathbb{F}_q.$ Define $$ f(x,y)=xy+g(x)+h(y)\quad\forall (x,y)\in\mathbb{F}_q\times\mathbb{F}_q, $$ $$ N(x)=\left\{y\in\mathbb{...
user avatar
1 vote
1 answer
88 views

Largest eigenvalue of a bipartite biregular graph

Let $G$ be a bipartite biregular graph. That is, $G$ is a bipartite graph with vertex sets $V_1$ and $V_2$ such that every vertex in $V_1$ has degree $d_1$ and every vertex in $V_2$ has degree $d_2$. ...
user avatar
  • 687
0 votes
1 answer
44 views

Ordering vertices of a bipartite digraph satisfying a specific property

Let $D$ the bipartite digraph with vertices bipartitions $A$ and $B$ such that it has only arcs of $A$ to $B$. It easy to see that $D$ is acyclic (not contains directed cycle). I know that $D$ has a ...
user avatar
  • 69
1 vote
2 answers
57 views

Do balanced matrices contain as a sub-matrix a permutation of a 2 by 2 identity? [closed]

Let $M$ be a $n$ by $n$ matrix whose entries are $0$ or $1$, and such that it contains no row whose entries are all $0$, and no column whose entries are all $1$. Then, is it true that if $n\geq 2$, $M$...
user avatar
  • 205
6 votes
1 answer
99 views

$4$-choosability of $K_{10,10}$

A graph is $k$-choosable if no matter how one assigns a list of $k$ colors to each vertex, the vertices in the graph can be coloured in a way that each vertex receives a colour from its list and any ...
user avatar
  • 2,547
0 votes
1 answer
40 views

Is this graph a bipartite graph?

Graph This question has come up in a CS exam that I have to take, however my solution is different from the one given and I can't see why I'm incorrect. I'd love to know what someone else thinks!
user avatar
0 votes
0 answers
51 views

A simple bipartite planar graph having no cycle of length shorter than $5$ satisfies $|E| \le \dfrac{3}{2} |V| -3.$ [duplicate]

Let $G = (V,E)$ be a simple bipartite planar graph having no cycle of length shorter than $5$ then it satisfy the following relation: $$|E| \le \dfrac{3}{2} |V| -3$$ The observations I have done: ...
user avatar
  • 11.9k
1 vote
1 answer
88 views

Prove Herschel graph is nonhamiltonian

Let us denote by $c(G)$ the number of components of graph $G$. Theory: For a hamiltonain graph we have $c(G-S)\leq|S|$ for any set $S$ of vertices of $G$. How can I show that Herschel graph is ...
user avatar
1 vote
2 answers
55 views

Prove that described graph contains $K_{2, t}$ as spanning subgraph

Let us consider graph $G$ that doesn't have multi edges and loops. Let it satisfy following inequality $$\sum_{x\in V(G)} \binom{\deg(x)}{2} \ge (t - 1) \cdot \binom{n}{2} + 1$$ then prove that $G$ ...
user avatar
1 vote
1 answer
40 views

If G is n regular, then G has n disjoint perfect matchings.

Let G be a bipartite simple graph show that: If G is n regular, then G has n paarwise disjoint perfect matchings. It's firstly easy to show that G has a perfect matching by using Hall’s Theorem, $|N(...
user avatar
1 vote
0 answers
48 views

Number of distinct perfect matching in a d-regular graph.

I have a claim that every d-regular bipartite graph has at least d! distinct perfect matchings. Is this claim is true? if yes then can somebody tell me the proof? Actually there is a problem that ask ...
user avatar
0 votes
0 answers
29 views

Can we convert 'possible bipartite' question to 'max flow' question

Ok, I am in dangerous waters :) I just began looking into popular graph interview questions and came across this classical one ...
user avatar
  • 101
3 votes
0 answers
65 views

Maximal number of intersections within a bipartite graph

Consider $n$ line segments in the Cartesian plane. For $1\leq k\leq n$, the $k$-th line segment is drawn from $(k,0)$ to $(x_k,1)$, where $\{x_1,x_2,...,x_k\}$ is a permutation of $\{1,2,...,n\}$. ...
user avatar
1 vote
1 answer
104 views

Partition of the edges of a $4$-regular graph

The edges of every $4$-regular non-directed graph can be divided into two sets, so that removing any vertex with its edges removes two edges from one set and two edges from the other. Could someone ...
user avatar
  • 85
2 votes
1 answer
41 views

Every bipartite Eulerian graph is a Hamilton graph

This is a true/false question I'm trying to solve to prepare for my exam. Could someone confirm my answer and help me prove it? What I think: false, but I can not come up with an example.
user avatar
  • 85
0 votes
0 answers
44 views

complement of a complete bipartite graph

I am a beginner at the topics, so I need some helps to understand. For example $K_{1 ,7}$ is a complete bipartite graph. Express the number of edges in $K_{1,7}^C$. I know that : $The~number ~of ~...
user avatar
  • 35
0 votes
1 answer
41 views

Assignment problem with multiple assignments and constraints

I have a bi-partite graph $G=(P \cup C,E)$ where $P$ contains 'parents', these parents are in pairs, but count as one vertex, and are to be matched with a number of children in the set $C$. I want to ...
user avatar
  • 31
0 votes
0 answers
46 views

Calculate the number of possible ways to write numbers 1, 2 and 3 on vertices so the graph becomes beautiful.

Given an undirected unweighted graph consisting of n vertices and m edges. we have to write a number on each vertex of the graph. Each number should be 1 , 2 or 3. The graph becomes beautiful if for ...
user avatar
  • 816
2 votes
3 answers
474 views

Why isn't this graph bipartite?

This is a very silly question but I can't seem to figure it out. Let $G$ be the graph with 6 nodes and 3 edges where 1 is connected to 4, 2 to 5 and 3 to 6. Le $ U = \{1,2,3\}$ and $V=\{4,5,6\}$. Then ...
user avatar
0 votes
1 answer
51 views

How many pairs of intersecting intervals can be chosen from two finite sets of disjoint intervals?

Let $$ \mathcal{K} := \{ I \cap J \mid I \in \mathcal{I}, J \in \mathcal{J} \} \setminus \{ \emptyset\},$$ where $\mathcal{I}$ is a finite set of disjoint real intervals, and so is $\mathcal{J}$. ...
user avatar
  • 47
1 vote
0 answers
76 views

Graph coloring where a maximum of 2 neighboring nodes can have the same color.

We are given a graph where each node can have at most 3 edges. We want to color this graph into 2 colors such that each node can have at most one neighbor with the same color as itself. How to prove ...
user avatar
1 vote
1 answer
48 views

Hungarian algorithm / assignment problem with cost function depending on resultant matching

The standard Hungarian algorithm solves the problem of assigning n workers to n jobs with a given cost function. In my variant, the cost function depends on the final matching produced by the ...
user avatar
  • 111
0 votes
1 answer
50 views

Existence of a path of length $n/2$ in every bipartite graph with $d(A,B)=1/2$.

Claim: Let $G=A\cup B$ be a balanced bipartite graph with $e(A,B) \geq n/2 $ then $G$ has a path of length $n/2$. I know about the erdos-gallai theorem that would net a path of length $n/4$. By noting ...
user avatar
  • 85
1 vote
1 answer
83 views

Same edge-connectivity and the minimum degree in bipartite graph

Let $G$ be a $n$-order bipartite graph. $\kappa'(G)$ is an edge-connectivity of $G$, and $\delta(G)$ is the minimum degree of $G$. I want to prove the following theorem: If $\delta(G) \geq \frac{n}{4}...
user avatar
  • 619
0 votes
0 answers
80 views

How a perfect matching M corresponds to a bijection between graphs.

I am reading an article, and I am relatively novice in graph theory. Consider two isomorphic graphs $G= (U,D)$ and $H= (V,E)$ of order $n$ and size $e$. Denote by $K_{U\cup V}$ the complete bipartite ...
user avatar
0 votes
1 answer
34 views

Proofing Decide Injective Coloring Problem is NP-complete for perfect elimination bipartite graphs?

So the proof goes like this For a graph $G=(V,E)$, $V=\{v_1,v_2,...,v_n\}$, $E=\{e_1,e_2,...,e_m\}$ having a chromatic number $X(G)$ we construct a perfect elimination bipartite graph $H$, using ...
user avatar
1 vote
0 answers
46 views

What is perfect elimination bipartite graph?

I am not a Maths guy, and I was required to read a paper on Graph Theory. Now after few pages the definition of perfect elimination bipartite graph comes up, no matter how hard I try grasp the ...
user avatar
2 votes
1 answer
114 views

Regular, connected, bipartite graph with no Hamilton cycle

Find an example of a graph $G$ with 3 or more vertices that is regular, connected, bipartite, and contains no Hamilton cycle. Please give me a hint. What I've got so far: Since $G$ is regular and ...
user avatar
2 votes
2 answers
59 views

Random bipartite graph with lower bounded degrees

Let $i$ be a positive integer and $V_1, V_2$ be the vertex sets of a bipartite graph. We want to sample uniformly at random a bigraph in the set of bigraphs with vertex set $V_1 \cup V_2$ such that ...
user avatar
  • 618
1 vote
1 answer
73 views

Is the following a matroid?

If I have a bipartite graph $G = (L \cup R, E)$, then there is a matroid on ground set $L$ whose independent sets are the matchable subsets of $L$. That is, $A \subseteq L$ is independent if there is ...
user avatar
0 votes
0 answers
41 views

What is the definition of a unbalanced bipartite graph?

What is the definition of a unbalanced bipartite graph? From what i can read it is that the two disjoint set of vertices have different sizes Is this true: any bipartite graph with unbalanced vertex ...
user avatar
0 votes
1 answer
57 views

Closed form expression‎ of double-way matching problem (Special case of derangement)

Is there a "closed form expression‎" for below problem ? Problem : "N" guests gave their raincoats and their umbrellas to the doorman at the entrance of the “Marlinspike” mansion ...
user avatar
2 votes
1 answer
93 views

Bipartite graph with exactly one perfect matching.

$\textbf{Problem:}$ Find all bipartite graphs $G[X,Y]$ satisfying the following properties: $1.$ $|X|=|Y|$, where $|X|\ge 2$ and $|Y|\ge 2$. $2.$ All vertices have degree three except for two vertices ...
user avatar
3 votes
1 answer
270 views

Using Graph Theory to solve an IMO 2021 problem

Here is a question from IMO 2021: Let $n>100$ be an integer. Ivan writes the numbers $n,n+ 1,\dots,2n$ each on different cards. He then shuffles these $n+ 1$ cards, and divides them into two piles....
user avatar
  • 265

1
2 3 4 5
13