A hypergraph H = is called 2-colorable if its vertices can be 2-colored so that no hyperedge is monochromatic. Every bipartite graph G = 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. A hypergraph in which some hyperedges are singletons is obviously not 2-colorable; to avoid such trivial obstacles to 2-colorability, it is common to consider hypergraphs that are essentially 2-colorable, i.e., they become 2-colorable upon deleting all their singleton hyperedges. A hypergraph is called balanced if it is essentially 2-colorable, and remains essentially 2-colorable upon deleting any number of vertices. Formally, for each subset U of V, define the restriction of H to U as the hypergraph HU = where . Then H is called balanced iff HU is essentially 2-colorable for every subset U of V. Note that a simple graph is bipartite iff it is 2-colorable iff it is balanced.
Definition by odd cycles
A cycle in a hypergraph is a cyclic alternating sequence of distinct vertices and hyperedges:, where every vertex vi is contained in both ei−1 and ei. The number k is called the length of the cycle. A hypergraph is balanced iff every odd-length cycle C in H has an edge containing at least three vertices of C. Note that in a simple graph all edges contain only two vertices. Hence, a simple graph is balanced iff it contains no odd-length cycles at all, which holds iff it is bipartite. Berge proved that the two definitions are equivalent; a proof is also available here.
Properties
Some theorems on bipartite graphs have been generalized to balanced hypergraphs.
In every balanced hypergraph, the degree equals the chromatic index. This generalizes a theorem of Konig on bipartite graphs.
Every balanced hypergraph satisfies a generalization of Hall's marriage theorem: it admits a perfect matching iff for all disjoint vertex-sets V1, V2, if for all edges e in E, then |V2| ≥ |V1|. See Hall-type theorems for hypergraphs.
Every balanced hypergraph with maximum degreeD, can be partitioned into D edge-disjoint matchings.
A k-fold transversal of a balanced hypergraph can be expressed as a union of k pairwise-disjoint transversals, and such partition can be obtained in polynomial time.
Comparison with other notions of bipartiteness
Besides balance, there are alternative generalizations of bipartite graphs. 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. Obviously every bipartite graph is 2-colorable. The properties of bipartiteness and balance do not imply each other. Balance does not imply bipartiteness. Let H be the hypergraph: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. Bipartiteness does not imply balance. For example, let H be the hypergraph with vertices and edges:It is bipartite by the partition X=, Y=. But is not balanced. For example, if vertex 1 is removed, we get the restriction of H to, which has the following hyperedges: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 =, and no edge of C contains all three vertices 2,3,4 of C. Tripartiteness does not imply balance. For example, let H be the tripartite hypergraph with vertices,, and edges:It is not balanced since if we remove the vertices 2,3,6, the remainder is:which is not colorable since it is a 3-cycle. Another way to see that it is not balanced is that It contains the odd-length cycle C =, and no edge of C contains all three vertices 1,4,5 of C.
A hypergraph is called totally balanced if every cycle C in H of length at least 3 has an edge containing at least three vertices of C. A hypergraph H is totally balanced iff every subhypergraph of H is a tree-hypergraph.
Normal hypergraphs
The Konig property of a hypergraph H is the property that its minimum vertex-cover has the same size as its maximum matching. The Kőnig-Egervary theorem says that all bipartite graphs have the Konig property. The balanced hypergraphs are exactly the hypergraphs H such that every partial subhypergraph of H has the Konig property. If every partial hypergraph of H has the Konig property, then H is called a normal hypergraph. Thus, totally-balanced implies balanced, which implies normal.
