Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Bipartite hypergraph
Summary
In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph.
Property B
The weakest definition of bipartiteness is also called 2-colorability. A hypergraph H = (V, E) is called 2-colorable if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge meets both X and Y. Equivalently, the vertices of H can be 2-colored so that no hyperedge is monochromatic. Every bipartite graph G = (X+Y, E) is 2-colorable: each edge contains exactly one vertex of X and one vertex of Y, so e.g. X can be colored blue and Y can be colored yellow and no edge is monochromatic.
The property of 2-colorability was first introduced by Felix Bernstein in the context of set families; therefore it is also called Property B.
A stronger definition of bipartiteness is: a hypergraph is called bipartite if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge contains exactly one element of X. Every bipartite graph is also a bipartite hypergraph.
Every bipartite hypergraph is 2-colorable, but bipartiteness is stronger than 2-colorability. Let H be a hypergraph on the vertices {1, 2, 3, 4} with the following hyperedges:{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }This H is 2-colorable, for example by the partition X = {1,2} and Y = {3,4}. However, it is not bipartite, since every set X with one element has an empty intersection with one hyperedge, and every set X with two or more elements has an intersection of size 2 or more with at least two hyperedges.
Hall's marriage theorem has been generalized from bipartite graphs to bipartite hypergraphs; see Hall-type theorems for hypergraphs.
An stronger definition is: given an integer n, a hypergraph is called n-uniform if all its hyperedges contain exactly n vertices. An n-uniform hypergraph is called n-partite if its vertex set V can be partitioned into n subsets such that each hyperedge contains exactly one element from each subset.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.