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

750 questions
Filter by
Sorted by
Tagged with
1 vote
38 views

### Is colour smoothness equivalent to finding a cover via disjoint cycles?

Let $G$ be a finite bipartite graph, with colouring function $c \colon V(G) \to \{-1, 1\}$. I want to consider the problem of finding vertex-disjoint cycles whose union spans $G$. We have the ...
• 117
31 views

### Value range of dual variables in Jonker-Volgenant algorithm for solving linear assignment problem

In A shortest augmenting path algorithm for dense and sparse linear assignment problems an algorithm for the Linear Assignment Problem is given, with a $O(N^3)$ time complexity (where $N$ is the "...
• 161
1 vote
43 views

### Zarankiewicz’s conjecture

The Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. A few years later, Zarankiewicz published a formula that provided a solution to ...
• 525
58 views

### Number of edges in planar bipartite graph.

Suppose G=(V,E) is a planar bipartite graph such that $V_1$ and $V_2$ are the partite sets. Suppose for all $a \in V_1$, $deg(a)\le p$ and for all $b \in V_2$, $deg(b)\le q$. If $|V_1|=x$ and $|V_2|=y$...
33 views

• 113
48 views

### $G(n,1/2)$ has a bipartite subgraph with at least $n^2/8+Cn^{3/2}$ edges

I want to show that with probability converging to $1$, $G(n,1/2)$ has a bipartite subgraph with at least $n^2/8+Cn^{3/2}$ edges for some positive constant $C$. The hint for this is to use a greedy ...
• 527
33 views

### Hamiltonian graph on a $8\times 8$ chessboard with upper left corner and bottom right corner square removed

Suppose we are given the setup in the title. Two squares are adjacent if and only if they share a common edge. I want to find out whether the obtained graph considering squares as nodes would be ...
• 79
29 views

### Prove that for complete biclique Ki,j that ∆(Ki,j) = χ′(Ki,j).

I am trying to prove it by contradiction. Proof: "Assume that ∆(Ki,j) != χ′(Ki,j) for a complete biclique (Ki,j). If ∆(Ki,j) > χ′(Ki,j), it implies that the minimum number of colors needed to ...
1 vote
29 views

### Terminology for a "semi-bipartite" graph strucure (graph theory)

Let $G$ be a finite graph whose vertices can be divided into two disjoint sets $U$ and $V$ such that a vertex in $V$ can be connected to any vertex in $G$, but a vertex in $U$ can be connected only to ...
• 111
1 vote
33 views

### Correct Counting of Independent Sets in a Complete Bipartite Graph $(K_{n, m})$

I'm diving into graph theory and am currently focused on understanding independent sets within complete bipartite graphs. Specifically, I've been pondering over how to accurately count the total ...
• 109
62 views

• 85
178 views

278 views

### Proof of statement regarding bipartite graphs

I'm trying to prove the following proposition as an exercise, and I'm stuck at some point. Let $G$ be a graph that doesn't contain $C_3$ or $P_4$ as an induced subgraph. Then $G$ is bipartite. My ...
• 123
88 views

### Bipartite graphs coloring

I was asked about an elementary (math olympiad) problem regarding members and committees, which can be formulated as the following graph-theoretic problem. Given a bipartite graph $(V_1\cup V_2, E)$, ...
• 1,219
1 vote
108 views

• 2,085
1 vote
73 views

### Prove bipartite graph with maximum degree d is a subgraph of a d regular bipartite graph

How can I show that every bipartite graph of maximum degree d is a subgraph of some d-regular bipartite graph. If something I'm saying could be better mathematically phrased, please let me know. Let'...
• 784
1 vote
66 views

### Finding the set that violates Hall’s condition in a bipartite graph.

If I have a bipartite graph for which it is given that there does not exist any complete matching. This implies that Hall’s condition is not satisfied for this graph. So, there must be atleast one set ...
• 751
1 vote
35 views

### Hamiltonicity of bipartite graphs maximum degree $3$, where $X$ or $Y$ is a clique

I'm quite new to graph theory and NP-complete proofs. I stumbled across NP-completeness on hamiltonicity of bipartite graphs with maximum degree $3$ and was wondering whether the same applies to ...
• 13
127 views

### Bondy, Murty Graph Theory exercise 16.2.12 (by Noga Alon)

Let $G = (U\sqcup V, E)$ be a bipartite graph in which each vertex of $U$ is of odd degree. Suppose that any two vertices of $U$ have an even number of common neighbours. Show that $G$ has a matching ...
• 581
1 vote
65 views

### Variant of vertex cover in bipartite graphs [closed]

I have this problem, and I am not sure whether it is known. Given a bipartite graph $G(U, V, E)$. Define two sets $V_{e}, V_{o} \subseteq V$ such that $V_{e}$ and $V_{o}$ are disjoint. Now, define ...
• 19
46 views

### How can we use a cartesian product in the definition for bipartite graph when its elements are tuples and edges can be sets?

I have learnt that in a bipartite graph, we can partition vertices into 2 sets $V_1$ and $V_2$, and $E \subseteq V_1 \times V_2$. However, the cartesian product is a set of tuples, and edges (in an ...
• 2,533
251 views

### Prove that all graphs with Degree Sequence $(2,2,2,2,2,2,2)$ have an odd cycle.

I've been asked to prove that a graph with Degree Sequence $(2,2,2,2,2,2,2)$ [2-regular, 7 vertices] cannot be bipartite. I know that bipartite graphs cannot have any cycles of odd length. I'm fairly ...
1 vote
175 views

### No eigenvalue of a graph is larger than the maximum degree

This is exercise 1.1.24 in "Graph Theory" by Bondy and Murty: $(a)$ No eigenvalue of a Graph $G$ has absolute value greater than $\Delta$ $(b)$ If $G$ is a connected graph and $\Delta$ is ...