Linked from

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

• Complete graphCompared with: A bipartite graph with at least three vertices cannot be complete.

• Graph (discrete mathematics)Broader topic: The partition captures relationships between two distinct classes of entities.

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

• Assignment problemNarrower topic: Agents and tasks form the two vertex sets; edges represent feasible assignments.

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

• HypergraphCompared with: Incidence graphs encode hypergraphs as ordinary bipartite graphs.

• Bipartite matchingNarrower topic: Its two vertex sets are the sides that a matching pairs.

• Chromatic numberBroader topic: Every nonempty bipartite graph has chromatic number two, unless it has no edges.

• Simple graphBroader topic: This simple-graph structure models relationships between two distinct kinds of entities.

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

• Dependency graphCompared with: It can model components and requirements separately, unlike a general dependency graph.

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

• Odd cycleCompared with: A graph is bipartite exactly when it contains no odd cycle.

• Undirected graphBroader topic: Its undirected edges encode relationships between two distinct classes.

• David GaleNarrower topic: Matching problems can be represented as selecting compatible edges between two groups.

• Brooks' theoremBroader topic: Bipartite structure often supplies a coloring with two colors, including in low-degree cases.

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

• Regular graphCompared with: Bipartiteness concerns edge placement, independent of whether degrees are equal.

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

• Hungarian algorithmNarrower topic: The algorithm's assignments are edges between two disjoint groups.

• Kőnig's theoremNarrower topic: The theorem applies precisely to graphs with this two-part structure.

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

• Dinitz theoremNarrower topic: Rows and columns form the two vertex classes in the graph model behind the proof.

• Generalized Petersen graphCompared with: Odd rim cycles often prevent generalized Petersen graphs from being bipartite.

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

• Homogeneous networkCompared with: Its two structurally distinct vertex sets make it a common nonhomogeneous case.

• Multilayer and multiplex networksCompared with: Some heterogeneous networks can be represented as bipartite layers, unlike multiplex layers sharing node identities.

• Stable matching problemNarrower topic: Two-sided matching problems represent possible partnerships as edges between distinct groups.