Balanced hypergraph: Difference between revisions

Revision as of 08:10, 2 July 2020

Revision as of 19:24, 2 July 2020

Line 20:

== Properties ==

Some theorems on bipartite graphs have been generalized to balanced hypergraphs.<ref>{{Cite journal|last=Berge|first=Claude|last2=Vergnas|first2=Michel LAS|date=1970|title=Sur Un Theorems Du Type König Pour Hypergraphes|url=https://nyaspubs.onlinelibrary.wiley.com/doi/abs/10.1111/j.1749-6632.1970.tb56451.x|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="lp2lp">{{Cite Lovasz Plummer}}</ref>{{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|url=http://www.sciencedirect.com/science/article/pii/0012365X72900064|journal=Discrete Mathematics|language=en|volume=2|issue=3|pages=253–267|doi=10.1016/0012-365X(72)90006-4|issn=0012-365X}}</ref> This generalizes a theorem of Konig on bipartite graphs.

Line 55:

== References ==

{{reflist}}

[[Category:Hypergraphs]]