Bipartite hypergraph

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 fo 2-colorability was first introduced by Felix Bernstein in the context of set families;[1] therefore it is also called Property B.

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.[2][3]

To see that this sense 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 exactly-2-colorable, 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.

Every bipartite graph G = (X+Y, E) is exactly-2-colorable.

Hall's marriage theorem has been generalized from bipartite graphs to exactly-2-colorable hypergraphs; see Hall-type theorems for hypergraphs.

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. [4] An alternative term is rainbow-colorable.[5]

To see that n-partiteness is stronger than exact-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} }

This H is 3-uniform. It is exactly-2-colorable by the partition X = {1} and Y = {2,3,4}. However, it is not 3-partite: in every partition of V into 3 subsets, at least one subset contains two vertices, and thus at least one hyperedge contains two vertices from this subset.

There are other natural generalizations of bipartite graphs. A hypergraph is called balanced if it is essentially 2-colorable, and remains essentially 2-colorable upon deleting any number of vertices (see Balanced hypergraph).

The properties of bipartiteness and balance do not imply each other.

Bipartiteness does not imply balance. For example, let H be the hypergraph with vertices {1,2,3,4} and edges:

{ {1,2,3} , {1,2,4} , {1,3,4} }

It is bipartite by the partition X={1}, Y={2,3,4}. But is not balanced. For example, if vertex 1 is removed, we get the restriction of H to {2,3,4}, which has the following hyperedges;

{ {2,3} , {2,4} , {3,4} }

It is not 2-colorable, since in any 2-coloring there are at least two vertices with the same color, and thus at least one of the hyperedges is monochromatic.

Another way to see that H is not balanced is that it contains the odd-length cycle C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), and no edge of C contains all three vertices 2,3,4 of C.

Balance does not imply bipartiteness. Let H be the hypergraph:

{ {1,2} , {3,4} , {1,2,3,4} }

it is 2-colorable and remains 2-colorable upon removing any number of vertices from it. However, It is not bipartite, since to have exactly one green vertex in each of the first two hyperedges, we must have two green vertices in the last hyperedge.

• Matching in hypergraphs
• Vertex cover in hypergraphs