Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
|||
Line 22:
Some theorems on bipartite graphs have been generalized to balanced hypergraphs.<ref>{{Cite journal|last1=Berge|first1=Claude|last2=Vergnas|first2=Michel LAS|date=1970|title=Sur Un Theorems Du Type König Pour Hypergraphes|journal=Annals of the New York Academy of Sciences|language=en|volume=175|issue=1|pages=32–40|doi=10.1111/j.1749-6632.1970.tb56451.x|issn=1749-6632}}</ref><ref name="lp" />{{Rp|468–470}}
* In every balanced hypergraph, the minimum [[Vertex cover in hypergraphs|vertex-cover]] has the same size as its maximum [[Matching in hypergraphs|matching]]. This generalizes the [[Kőnig's theorem (graph theory)|Kőnig-Egervary theorem]] on bipartite graphs.
* In every balanced hypergraph, the [[Degree (graph theory)|degree]] (= the maximum number of hyperedges containing some one vertex) equals the [[Edge coloring|chromatic index]] (= the least number of colors required for coloring the hyperedges such that no two hyperedges with the same color have a vertex in common).<ref>{{Cite journal|last=Lovász|first=L.|date=1972-06-01|title=Normal hypergraphs and the perfect graph conjecture|journal=Discrete Mathematics|language=en|volume=2|issue=3|pages=253–267|doi=10.1016/0012-365X(72)90006-4|issn=0012-365X|doi-access=free}}</ref> This generalizes a theorem of Konig on bipartite graphs.
* Every balanced hypergraph satisfies a generalization of [[Hall's marriage theorem]]:<ref name=":1" /> it admits a perfect matching iff for all disjoint vertex-sets ''V''<sub>1</sub>, ''V''<sub>2</sub>, if <math>|e\cap V_2| \geq |e\cap V_1|</math> for all edges ''e'' in ''E'', then |''V''<sub>2</sub>| ≥ |''V''<sub>1</sub>|. See [[Hall-type theorems for hypergraphs]].
* Every balanced hypergraph with maximum degree ''D'', can be partitioned into ''D'' edge-disjoint matchings.<ref name=":0" />{{Rp|Chapter 5}}<ref name=":1" />{{Rp|Corollary 3}}
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.<ref>{{Cite journal|last1=Dahlhaus|first1=Elias|last2=Kratochvíl|first2=Jan|last3=Manuel|first3=Paul D.|last4=Miller|first4=Mirka|date=1997-11-27|title=Transversal partitioning in balanced hypergraphs|url=http://www.sciencedirect.com/science/article/pii/S0166218X97000346|journal=Discrete Applied Mathematics|language=en|volume=79|issue=1|pages=75–89|doi=10.1016/S0166-218X(97)00034-6|issn=0166-218X|doi-access=free}}</ref>
== Comparison with other notions of bipartiteness ==
| |||