Linked from

The 35 pages that link to Bipartite graph, each with the reason it gives.

• Incidence matrixRelated: An incidence matrix is itself the adjacency matrix of a graph's vertex-edge bipartite graph.

• Breadth-first searchRelated: Alternating distance layers can test whether a graph is bipartite.

• Edge coloringRelated: Bipartite graphs obey a particularly sharp bound on their edge chromatic number.

• Hall's marriage theoremRelated: Sets and their possible representatives become the two vertex classes, joined by membership edges.

• Perfect matchingRelated: Many matching problems, including marriage problems, use this structure.

• Stable marriage problemRelated: Potential pairings connect the two sides of the matching problem.

• Transportation problemRelated: Sources and destinations form the two vertex sets underlying the standard model.

• Graph homomorphismRelated: A graph maps to the two-vertex complete graph exactly when it is bipartite.

• Szemerédi–Trotter theoremRelated: Point–line incidences form a bipartite graph whose edges encode incidences.

• Erdős–Stone theoremRelated: Every non-bipartite forbidden graph has chromatic number at least three, producing a positive quadratic density threshold.

• Maximum-cardinality matchingRelated: Bipartite structure enables stronger theorems and faster matching algorithms.

• Edge coverRelated: Bipartite edge-cover problems can be solved through maximum bipartite matching.

• Stable roommates problemRelated: Marriage matching is bipartite; roommate preferences allow every person to pair with anyone else.

• De Bruijn–Erdős theorem (graph theory)Related: The theorem implies that a graph is bipartite exactly when all its finite subgraphs are bipartite.

• Grimm's conjectureRelated: Connect each composite to its prime divisors to represent the assignment problem.